C语言:杨氏矩阵中查找某数(时间复杂度小于O(N))

这篇具有很好参考价值的文章主要介绍了C语言:杨氏矩阵中查找某数(时间复杂度小于O(N))。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:

有一个数字矩阵二维数组),

矩阵的每行从左到右是递增的
矩阵从上到下是递增的
请编写程序在这样的矩阵中查找某个数字是否存在,

要求:时间复杂度小于O(N)

                    

 =========================================================================

                       

思路:

总体思路:

(1).

自定义函数:

           

实现逻辑

因为是杨氏矩阵,所以一行中最右边的数是最大的

这个最大值如果比要找的值都小的话,那就可以排除这一行

列也是同理

                  

函数参数接收 二维数组名要查找的数

存放矩阵行数的变量的指针(地址)存放矩阵列数的变量的指针(地址)

                  

通过两个变量找出二维数组第一行的最大值

              

使用 while循环 ,如果未查找到 二维数组的最大行数 且 列数未到最小列

行的最右边的数是最大的列逐渐判断直到最小列

继续查找

          

(2).

while循环中

                

使用 if条件判断语句判断第一行最大值是否小于要找的值

          

如果小于那么这一行不可能有要查找的值,可以排除这一行指针移到下一行

          

如果最大值大于要查找的值,那么该值就在这一行,逐渐移动列数在改行进行查找

          

如果要查找的值直接就和该行最大值相等通过调整行数和列数找到了

          

通过 矩阵的行数列数变量的指针 设置找到的行数和列数

                 

跳出循环还未找到的话,则将k的“坐标”设置为(-1,-1)表未找到

                       

(3).

主函数:

          

给出一个杨氏矩阵二维数组),

            

输入要在矩阵中找的数

               

设置矩阵的 行 和 列

             

使用自定义函数进行查找

函数参数二维数组名要查找的数

矩阵行数变量的指针(地址)矩阵列数变量的指针(地址)

                      

通过函数的查找情况打印相应情况

                


                 

第一步:

自定义函数:

           

实现逻辑

因为是杨氏矩阵,所以一行中最右边的数是最大的

这个最大值如果比要找的值都小的话,那就可以排除这一行

列也是同理

                  

函数参数接收 二维数组名要查找的数

存放矩阵行数的变量的指针(地址)存放矩阵列数的变量的指针(地址)

                  

通过两个变量找出二维数组第一行的最大值

              

使用 while循环 ,如果未查找到 二维数组的最大行数 且 列数未到最小列

行的最右边的数是最大的列逐渐判断直到最小列

继续查找

                     

实现代码:
#include <stdio.h>

//自定义函数:
void young_table_search(int arr[3][3], int k, int* px, int* py)
{
	//通过两个变量找出二维数组第一行的最大值:
	//行和列是从0开始的,
	int x = 0; //二维数组的行,从第一行进行查找
	int y = *py - 1; //二维数组的列,从最大列开始查找,

	//使用 while循环 进行查找:
	while (x<=*px-1 && y>=0)
		//x<=*px-1  -- 未查找到最大行数
		//y>=0  --  未调整到最小列数
	{


	}
}

int main() 
{


	return 0;
}
实现图片:

C语言:杨氏矩阵中查找某数(时间复杂度小于O(N)),没事做道题:C语言,c语言,算法

                 


                 

第二步:

在while循环中:

                

使用 if条件判断语句判断第一行最大值是否小于要找的值

          

如果小于那么这一行不可能有要查找的值,可以排除这一行指针移到下一行

          

如果最大值大于要查找的值,那么该值就在这一行,逐渐移动列数在改行进行查找

          

如果要查找的值直接就和该行最大值相等通过调整行数和列数找到了

          

通过 矩阵的行数列数变量的指针 设置找到的行数和列数

                 

跳出循环还未找到的话,则将k的“坐标”设置为(-1,-1)表未找到

                     

实现代码:
#include <stdio.h>

//自定义函数:
void young_table_search(int arr[3][3], int k, int* px, int* py)
{
	//通过两个变量找出二维数组第一行的最大值:
	//行和列是从0开始的,
	int x = 0; //二维数组的行,从第一行进行查找
	int y = *py - 1; //二维数组的列,从最大列开始查找,

	//使用 while循环 进行查找:
	while (x<=*px-1 && y>=0)
		//x<=*px-1  -- 未查找到最大行数
		//y>=0  --  未调整到最小列数
	{
		if (arr[x][y] < k)
			//第一行最大值 小于 k
		{
			x++; //排除这一行,移到下一行
		}
		else if (arr[x][y] > k)
			//第一行最大值 大于 k
		{
			y--; //k就在这一行,移到列进行查找
		}
		else
			//找到了:把k的行和列赋给指针px和py
		{
			*px = x;
			*py = y;
			return;
		}
	}
	//自定义未找到的情况:
	*px = -1;
	*py = -1;
}

int main() 
{


	return 0;
}
实现图片:

C语言:杨氏矩阵中查找某数(时间复杂度小于O(N)),没事做道题:C语言,c语言,算法

                 


                 

第三步:

主函数:

          

给出一个杨氏矩阵二维数组),

            

输入要在矩阵中找的数

               

设置矩阵的 行 和 列

             

使用自定义函数进行查找

函数参数二维数组名要查找的数

矩阵行数变量的指针(地址)矩阵列数变量的指针(地址)

                      

通过函数的查找情况打印相应情况

                     

实现代码:
#include <stdio.h>

//自定义函数:
void young_table_search(int arr[3][3], int k, int* px, int* py)
{
	//通过两个变量找出二维数组第一行的最大值:
	//行和列是从0开始的,
	int x = 0; //二维数组的行,从第一行进行查找
	int y = *py - 1; //二维数组的列,从最大列开始查找,

	//使用 while循环 进行查找:
	while (x<=*px-1 && y>=0)
		//x<=*px-1  -- 未查找到最大行数
		//y>=0  --  未调整到最小列数
	{
		if (arr[x][y] < k)
			//第一行最大值 小于 k
		{
			x++; //排除这一行,移到下一行
		}
		else if (arr[x][y] > k)
			//第一行最大值 大于 k
		{
			y--; //k就在这一行,移到列进行查找
		}
		else
			//找到了:把k的行和列赋给指针px和py
		{
			*px = x;
			*py = y;
			return;
		}
	}
	//自定义未找到的情况:
	*px = -1;
	*py = -1;
}

int main() 
{
	//给出一个杨氏矩阵:
	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
	//					1 2 3
	//					4 5 6
	//					7 8 9

	//输入要找的数:
	int k = 0;
	scanf("%d", &k);

	//设置矩阵的行和列:
	int x = 3; //矩阵的行
	int y = 3; //矩阵的列

	//使用自定义函数进行查找:
	young_table_search(arr, k, &x ,&y);

	//根据情况大于相应情况:
	if (x==-1 && y==-1)
		//未找到
	{
		printf("未找到");
	}
	else
		//找到了
	{
		printf("找到了,它的下标为:第%d行 第%d列", x, y);
	}

	return 0;
}
实现图片:

C语言:杨氏矩阵中查找某数(时间复杂度小于O(N)),没事做道题:C语言,c语言,算法

                       

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

                        

最终代码和实现效果

最终代码:

#include <stdio.h>

//自定义函数:
void young_table_search(int arr[3][3], int k, int* px, int* py)
{
	//通过两个变量找出二维数组第一行的最大值:
	//行和列是从0开始的,
	int x = 0; //二维数组的行,从第一行进行查找
	int y = *py - 1; //二维数组的列,从最大列开始查找,

	//使用 while循环 进行查找:
	while (x<=*px-1 && y>=0)
		//x<=*px-1  -- 未查找到最大行数
		//y>=0  --  未调整到最小列数
	{
		if (arr[x][y] < k)
			//第一行最大值 小于 k
		{
			x++; //排除这一行,移到下一行
		}
		else if (arr[x][y] > k)
			//第一行最大值 大于 k
		{
			y--; //k就在这一行,移到列进行查找
		}
		else
			//找到了:把k的行和列赋给指针px和py
		{
			*px = x;
			*py = y;
			return;
		}
	}
	//自定义未找到的情况:
	*px = -1;
	*py = -1;
}

int main() 
{
	//给出一个杨氏矩阵:
	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
	//					1 2 3
	//					4 5 6
	//					7 8 9

	//输入要找的数:
	int k = 0;
	scanf("%d", &k);

	//设置矩阵的行和列:
	int x = 3; //矩阵的行
	int y = 3; //矩阵的列

	//使用自定义函数进行查找:
	young_table_search(arr, k, &x ,&y);

	//根据情况大于相应情况:
	if (x==-1 && y==-1)
		//未找到
	{
		printf("未找到");
	}
	else
		//找到了
	{
		printf("找到了,它的下标为:第%d行 第%d列", x, y);
	}

	return 0;
}

实现效果

C语言:杨氏矩阵中查找某数(时间复杂度小于O(N)),没事做道题:C语言,c语言,算法文章来源地址https://www.toymoban.com/news/detail-605824.html

到了这里,关于C语言:杨氏矩阵中查找某数(时间复杂度小于O(N))的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [数据结构-C语言] 算法的时间复杂度

    目录 1.算法的复杂度 2.时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 3、常见时间复杂度计算举例 3.1 冒泡排序 3.2 二分查找 3.3 阶乘递归 3.4 斐波那契数列 1.算法的复杂度 算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此 衡量一个算法的

    2024年02月02日
    浏览(46)
  • 感染法和广度优先搜索及时间复杂度分析 —— NC269999 小红走矩阵

    题目来源: 牛客周赛 Round 36 题目如下: 题目 小红走矩阵 小红来到了一个n∗m的矩阵,她初始站在左上角,每次行走可以按“上下左右”中的一个方向走一步,但必须走到和当前格子不同的字符,也不能走到矩阵外。 小红想知道,从左上角走到右下角最少需要走多少步?

    2024年04月17日
    浏览(41)
  • 算法 时间、空间复杂度的计算(C语言/小白/零基础/新手 + 例题)

    目录 1. 时间复杂度 计算时间复杂度( O(N))的方法:   例1:嵌套循环时间复杂度的计算      例2:双重循环时间复杂度的计算   例3:常熟循环的时间复杂度   例6:冒泡排序的时间复杂度   例7: 二分查找的时间复杂度   例8:斐波那契的时间复杂度         常见的时间

    2024年02月08日
    浏览(39)
  • 二分查找结果总是不对?一文帮你解决二分查找的边界问题&&数组移除元素太耗时间,双指针法为你打开新世界的大门,降时间复杂度为O(n)

      可能有粗心写的不正确的地方,或者因为技术有限写得不好的地方,欢迎大家批评指正,文章中给出的代码是本人自己写的leetcode中的代码,是代码的核心部分,如果放到本地编译器中,可能要加入mian()函数等内容。 LeetCode704二分查找    二分查找的思路非常简单,也就

    2024年02月08日
    浏览(66)
  • 时间复杂度和空间复杂度

    时间复杂度和空间复杂度是用来评估算法性能的两个重要指标。 时间复杂度(Time Complexity)是衡量算法执行时间随输入规模增长而增长的度量。它表示了算法解决问题所需的时间量级。常见的时间复杂度有: 常数时间复杂度 O(1):无论输入规模的大小,算法的执行时间都是固

    2024年01月17日
    浏览(47)
  • 算法的时间复杂度与空间复杂度

    1.算法效率 2.时间复杂度 3.空间复杂度 4.复杂度oj题目 1.算法效率 1.1 如何衡量一个算法的好坏 一辆车的好坏我们可以从价格,油耗...... 方面来衡量,但衡量一个算法的好坏我们该从哪一个方面入手呢?比如斐波那契数列: 斐波那契数列的递归实现方式非常简洁,但简洁一定

    2024年02月15日
    浏览(83)
  • 【算法基础】时间复杂度和空间复杂度

    1 算法的评价 2 算法复杂度 2.1 时间复杂度(Time Complexity) 2.1.1 如何计算时间复杂度: 2.1.2 常见的时间复杂度类别与示例 2.2 空间复杂度 2.2.1 如何计算空间复杂度 2.2.2 常见的空间复杂度与示例 3 时间复杂度和空间复杂度计算示例 例子1:计算数组中所有元素的和。 例子2:快

    2024年02月08日
    浏览(56)
  • 算法的时间复杂度和空间复杂度

    目录 本章重点 一 时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 2.3 常见的时间复杂度的计算 二 空间复杂度 三 常见复杂度对比 四 复杂度的oj练习 4.1 消失的数字 4.2 旋转数字 每一天都是人生限定,每一天都值得100%努力 (1)算法效率(2)时间复杂度(3)空间复

    2024年02月01日
    浏览(47)
  • 什么是时间复杂度和空间复杂度

    🍕博客主页:️自信不孤单 🍬文章专栏:数据结构与算法 🍚代码仓库:破浪晓梦 🍭欢迎关注:欢迎大家点赞收藏+关注 数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。 算法(Algorithm):就是定义良好的计算过程

    2023年04月15日
    浏览(42)
  • 算法之【时间复杂度】与【空间复杂度】

    目录 一、算法 1、算法定义 2、两种算法的比较 3、算法的特性 4、算法设计的要求 二、算法的复杂度 1、时间复杂度 1.1定义 1.2大O的渐近表示法 1.3推导大O阶方法 1.4最坏情况与平均情况 1.5常见的时间复杂度计算示例 🍂常数阶: 🍂线性阶:  🍂对数阶: 🍂平方阶: 2、空间

    2024年02月05日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包