【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码}

这篇具有很好参考价值的文章主要介绍了【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码}。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 

目录

 题目信息

题目分析:

法一:

遍历二维数组(低效)

思路

源码

 局限性

 法二:

对每一行二分查找(有所提效)

思路

 源码

局限性

法三:

利用一切有利条件使用二分查找

思路

源码

局限性

 二分查找源码:


 

 题目信息

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

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


题目分析:

        这道题是什么情况呢?其实就是说,有下面的这样一个满足要求的矩阵:

【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码},决胜oj,c语言,矩阵,算法,经验分享,数据结构

 

 干脆  , 更直观一点:


【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码},决胜oj,c语言,矩阵,算法,经验分享,数据结构

         也就是,在这样的矩阵(每一行从左到右递增,每一列从上到下递增)中查找一个特定的元素。

        如果找到,确定它的位置;如果找不到,输出  -1 ;

法一:

 

遍历二维数组(低效)

 

思路

        我们首先最容易想到的,也是最简单的方法,就是遍历数组,一个一个去试一试,看看能不能找到。

源码


#define ROW 5
#define COL 5

int main()
{
	int key;
	scanf("%d",&key);
	char arr[ROW][COL] = {{1,2,3,4,5},{4,5,6,7,8},{5,6,7,8,10},{10,11,12,13,14},{15,16,17,18,19}};
	int i = 0;
	for(i = 0;i < ROW;i++)
	{
		int j = 0;
		for(j = 0;j < COL;j++)
		{
			if(key ==arr[i][j])
			{
				printf("找到了,在%d行%d列\n",i,j);
				break;
			}
		}
	}
	
	return 0;
}

 

         【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码},决胜oj,c语言,矩阵,算法,经验分享,数据结构

         对照一下结果,代码是正确的。

【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码},决胜oj,c语言,矩阵,算法,经验分享,数据结构

 局限性

 

        经过计算,遍历算法的时间复杂度为O(N^2)

         虽然遍历算法思路简单易想,这样的时间复杂度太大,不再符合题目要求。

 法二:

 

对每一行二分查找(有所提效)

 

思路

        由于数组的每一行都是有序的,这样就满足了二分查找的使用条件,所以可以直接对每一行二分查找:

        直观一点:【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码},决胜oj,c语言,矩阵,算法,经验分享,数据结构

 源码


#define ROW 5
#define COL 5
#include<stdio.h>
#include<string.h>
int bi_search(int arr[ROW],int sz,int key)
{
	int f = 0;
	int left = 0;
	int right = sz-1;
	int mid = (left + right)/2;
	while(left<=right)
	{   
		mid = (left + right)/2;
		if(arr[mid] > key)
		{
			right = mid - 1;
		}
		else if(arr[mid] < key)
		{
			left = mid + 1;
		}
		else if(arr[mid] == key)
		{
			f = 1;
			return mid;
		}
	}
	if(f == 0)
	{
		return -1;
	}
}
int main()
{
	int key;
	scanf("%d",&key);
	int arr[ROW][COL] = {{1,2,3,4,5},{4,5,6,7,8},{5,6,7,8,10},{10,11,12,13,14},{15,16,17,18,19}};
	int i = 0;
	int f = 0;
	for(i = 0;i < ROW;i++)
	{
		int ret = bi_search(arr[i],COL,key);
		if(ret != -1)
		{
			f = 1;
			printf("找到了,在%d行%d列\n",i,ret);
		}
	}
	if(f == 0)
	{
		printf("找不到");
	}
	return 0;
}

         在实际动手写代码时,我也遇到了一些问题,比如刚开始把打印找不到放在循环内,结果出现了这样的结果:【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码},决胜oj,c语言,矩阵,算法,经验分享,数据结构

         这就挺尴尬的,解决办法是引入判断变量f,然后先假设找不到f初始化为0;如果找到,f置为1,如果直到循环完毕,f都没有被置为1,则就是整个数组都没有key;

局限性

        经计算,对每一行进行二分查找算法的时间复杂度为O(N log2(N))

虽然速度有所提升,但是效率仍然达不到题目要求。 

 

法三:

 

利用一切有利条件使用二分查找

 

思路

         我们可以先对行进行二分查找

        假设找9,在比9大的前一个元素前停下,由于行列都是从小到大递增的,所以可以断定后两行没有要找的元素9

 

  对行二分查找

【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码},决胜oj,c语言,矩阵,算法,经验分享,数据结构

 

 后两行没有9

 

 【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码},决胜oj,c语言,矩阵,算法,经验分享,数据结构

 

 接下来对行进行二分查找,但是我们发现所有的行都小于要查找的key,所以接下来只能对剩下的3行分别二分查找。

 

【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码},决胜oj,c语言,矩阵,算法,经验分享,数据结构 

 在这种n = 5 ,的情况下,我们发现时间复杂度并没有降低多少,我们分析一下:

        每一行二分,需要5次;

        而先列,进行排除;再行,需要4次;

但是在一般情况下,n可能很大,可能是100000,甚至更大,在这种情况下,程序有很大程度的提效。

 

 【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码},决胜oj,c语言,矩阵,算法,经验分享,数据结构

 时间复杂度N的趋势:

 【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码},决胜oj,c语言,矩阵,算法,经验分享,数据结构

源码

       我在写这个代码的时候遇到了一些问题,在对第一列进行二分查找后,在不再次遍历数组的情况下(不再增加时间复杂度),没有办法定位到合适的位置(在这个位置上,数组的后一个元素的大小大于key,数组前一个元素大小小于key,),你可以想一想,私信我交流。

局限性

         假设第k个找到合适位置,需要进行两次二分查找,时间复杂度是(log2(N)),剩下每一行都可能会出现key;

       

        但在此处,我选择对排除后的每一行进行二分查找,时间复杂度为(k*log2(k));

则时间复杂度的表达式为:

        T = log2(N)+   k*log2(k)  (k < N)

         最差情况,k == N,时间复杂度O(N* ( log2 (N) ) );

         最优解:k == 0,时间复杂度O(1);

        其实,我们可以设计更复杂的算法,这样可以进一步提高效率;

         提供一种思路:沿着对角线遍历n*n的矩阵,找到合适的停留点,这样又可以排除一部分可能:

【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码},决胜oj,c语言,矩阵,算法,经验分享,数据结构

 

         如果你可以巧妙利用题目信息,那么,即使有时间限制,oj题目对你来说一定不在话下!

         加油吧!


 

 二分查找源码:

int bi_search(int arr[ROW],int sz,int key)//参数分别是:要查找的行,数组元素的个数,要查找的对象
{
	int f = 0;
	int left = 0;
	int right = sz-1;
	int mid = (left + right)/2;
	while(left<=right)
	{   
		mid = (left + right)/2;
		if(arr[mid] > key)
		{
			right = mid - 1;
		}
		else if(arr[mid] < key)
		{
			left = mid + 1;
		}
		else if(arr[mid] == key)
		{
			f = 1;
			return 1;//如果找到,返回1
		}
	}
	if(f == 0)
	{
		return -1;//如果找不到,返回-1
	}
}

完~

 未经作者同意禁止转载文章来源地址https://www.toymoban.com/news/detail-756071.html

到了这里,关于【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码}的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包