Fork me on GitHub

算法(二位数组查找)

题目

在一个二位数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二位数组和一个整数,判断数组中是否含有该整数。

最简单的思路:就是遍历数组,找到即可。缺点:时间复杂度比较大
第二种思路:选择中间一个,然后进行判断,左右判断,这样时间复杂度有所减少。
第三种思路:从最右上角开始开始比较,这样每一次都会排出一行或者一列
,这样二位数组的范围逐渐在减少。如下图:
WechatIMG34.jpeg

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool find(int *martrix,int rows,int columns,int num){
int row = 0;
int column = columns-1;
if (martrix==NULL||rows<0||column<1) {
return false;
}
while (row<rows&&column<columns) {
if (martrix[row*columns+column]==num) {
return true;
}else if (martrix[row*columns+column]<num){
++row;
}else{
--column;
}
}
return false;
}

测试

1
2
3
int a[][4] = {{1,2,3,4},{5,6,9,10},{7,12,18,20},{9,13,19,30}};
bool isfind = find(a, 4, 4, 19);
printf("%d\n",isfind);
0%