剑指offer之二维数组中查找

1 问题

二维数组中查找:

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

列如:

1  2  8   9
2  4  9   12
4  7  10  13
6  8  11  15

2 分析

比如我们要找数字7, 我们先从右上角开始分析,如果要找的值比9小,我们在把列向左移动,然后再去把列向左移动,再去找8,然后发现还是比8小,我们依然向左移动,我们再去找到2,然后发现比2大,我们再把行向下移动,找到4,然后我们发现4还是比7小,我们再把行往下移动,以此类推,然后我们发现找到了7.

3 代码实现

#include <stdio.h>

int find(int a[][4], int rows, int  columns, int value)
{
if (a == NULL || rows <= 0 || columns <= 0)
{
return -1;
}
int i = 0;
int j = columns - 1;
while (i < rows 0 && j >= 0)
{
if (a[i][j] == value)
{
return 0;
}
else if (a[i][j] > value)
{
j--;
}
else
{
i++;
}
}
return -1;
}

int find1(int a[][4], int rows, int  columns, int value)
{
for (int i = 0; i < rows;)
{
for (int j = columns - 1; j >=0;)
{
if (a[i][j] == value)
{
return 0;
}
else if (a[i][j] > value)
{
j--;
}
else
{
i++;
}
}
}
return -1;
}
int main()
{
int a[4][4] = {{1, 2, 8, 9}, {2, 4, 9 , 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
int result1 = find(a, 4, 4, 11);
int result2 = find(a, 4, 4, 3);
printf("result1 is %d\n", result1);
printf("result2 is %d\n", result2);
int result3 = find(a, 4, 4, 11);
int result4 = find(a, 4, 4, 3);
printf("result3 is %d\n", result3);
printf("result4 is %d\n", result4);
return 0;
}

4 运行结果

result1 is 0
result2 is -1
result3 is 0
result4 is -1

5 总结

既然我们分析过程会发现行和列都会变,那么我们肯定需要用2个变量去表示行和列,那么我们肯定要找到便利得终止条件,就是变量行不能大于数组真正得行,然后列的话不能小于0,这个问题我一开始用得2个for,然后for里面写了i和j的变化,后面发现不好理解,然后如果以后我们只要涉及到for里面得i和j更加实际情况需要动态变化的,我们就不要用2个for循环了,我们直接用

while(终止条件) {i变化,j变化}里面改变i和j的值,也就是在while循环里面直接操刀i和j,一定要记住。

(0)

相关推荐