目录
题目信息
题目分析:
法一:
遍历二维数组(低效)
思路
源码
局限性
法二:
对每一行二分查找(有所提效)
思路
源码
局限性
法三:
利用一切有利条件使用二分查找
思路
源码
局限性
二分查找源码:
题目信息
有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在。
要求:时间复杂度小于O(N);
题目分析:
这道题是什么情况呢?其实就是说,有下面的这样一个满足要求的矩阵:
干脆 , 更直观一点:
也就是,在这样的矩阵(每一行从左到右递增,每一列从上到下递增)中查找一个特定的元素。
如果找到,确定它的位置;如果找不到,输出 -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;
}
对照一下结果,代码是正确的。
局限性
经过计算,遍历算法的时间复杂度为O(N^2)
虽然遍历算法思路简单易想,这样的时间复杂度太大,不再符合题目要求。
法二:
对每一行二分查找(有所提效)
思路
由于数组的每一行都是有序的,这样就满足了二分查找的使用条件,所以可以直接对每一行二分查找:
直观一点:
源码
#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;
}
在实际动手写代码时,我也遇到了一些问题,比如刚开始把打印找不到放在循环内,结果出现了这样的结果:
这就挺尴尬的,解决办法是引入判断变量f,然后先假设找不到f初始化为0;如果找到,f置为1,如果直到循环完毕,f都没有被置为1,则就是整个数组都没有key;
局限性
经计算,对每一行进行二分查找算法的时间复杂度为O(N log2(N))
虽然速度有所提升,但是效率仍然达不到题目要求。
法三:
利用一切有利条件使用二分查找
思路
我们可以先对行进行二分查找
假设找9,在比9大的前一个元素前停下,由于行列都是从小到大递增的,所以可以断定后两行没有要找的元素9
对行二分查找
后两行没有9
接下来对行进行二分查找,但是我们发现所有的行都小于要查找的key,所以接下来只能对剩下的3行分别二分查找。
在这种n = 5 ,的情况下,我们发现时间复杂度并没有降低多少,我们分析一下:
每一行二分,需要5次;
而先列,进行排除;再行,需要4次;
但是在一般情况下,n可能很大,可能是100000,甚至更大,在这种情况下,程序有很大程度的提效。
时间复杂度N的趋势:
源码
我在写这个代码的时候遇到了一些问题,在对第一列进行二分查找后,在不再次遍历数组的情况下(不再增加时间复杂度),没有办法定位到合适的位置(在这个位置上,数组的后一个元素的大小大于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的矩阵,找到合适的停留点,这样又可以排除一部分可能:
如果你可以巧妙利用题目信息,那么,即使有时间限制,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
未经作者同意禁止转载文章来源地址https://www.toymoban.com/news/detail-756071.html
到了这里,关于【C语言.oj刷题】有序#整型矩阵元素查找##{思路+C源码}的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!