题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
当我们需要解决一个复杂的问题时,一个很有效的办法就是从一个具体的问题入手,通过分析简单具体的例子,试图寻找普遍的规律。针对这个问题,我们不妨也从一个具体的例子入手。下面我们以在题目中给出的数组中查找数字7为例来一步步分析查找的过程。
我们发现如下规律:首先选取数组中右上角的数字。如果该数字等于要查找的数字,查找过程结束;如果该数字大于要查找的数字,剔除这个数字所在的列;如果该 数字小于要查找的数字,剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角,则每一次都在数组的查找范围中剔除一行或者一列,这样每一步都 可以缩小查找的范围,直到找到要查找的数字,或者查找范围为空。
把整个查找过程分析清楚之后,我们再写代码就不是一件很难的事情了。下面是上述思路对应的参考代码:
[cpp] view plaincopy
bool Find(int* matrix, int rows, int columns, int number)
{
bool found = false;
if(matrix != NULL && rows > 0 && columns > 0)
{
int row = 0;
int column = columns - 1;
while(row < rows && column >=0)
{
if(matrix[row * columns + column] == number)
{
found = true;
break;
}
else if(matrix[row * columns + column] > number)
-- column;
else
++ row;
}
}
return found;
}
在前面的分析中,我们每一次都是选取数组查找范围内的右上角数字。同样,我们也可以选取左下角的数字。感兴趣的读者不妨自己分析一下每次都选取左下角的查 找过程。但我们不能选择左上角或者右下角。以左上角为例,最初数字1位于初始数组的左上角,由于1小于7,那么7应该位于1的右边或者下边。此时我们既不 能从查找范围内剔除1所在的行,也不能剔除1所在的列,这样我们就无法缩小查找的范围。
二维数组的乘法实现可参考:http://www.cnblogs.com/heyonggang/p/3262069.html
实现代码如下:
1 #include<iostream>
2 using namespace std;
3
4 // 二维数组matrix中,每一行都从左到右递增排序,
5 // 每一列都从上到下递增排序
6 bool Find(int* matrix, int rows, int columns, int number)
7 {
8 bool found = false;
9
10 if(matrix != NULL && rows > 0 && columns > 0)
11 {
12 int row = 0;
13 int column = columns - 1;
14 while(row < rows && column >=0)
15 {
16 if(matrix[row * columns + column] == number)
17 {
18 found = true;
19 break;
20 }
21 else if(matrix[row * columns + column] > number)
22 -- column;
23 else
24 ++ row;
25 }
26 }
27
28 return found;
29 }
30
31 int main()
32 {
33 int matrix[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
34 bool result = Find((int*)matrix , 4 , 4 , 7); //这里实参是(int*)matrix
35 if(result == true)
36 printf("Passed.\n");
37 else
38 printf("Failed.\n");
39 return 0;
40
41 }
测试代码如下:
[cpp] view plaincopy
#include<iostream>
using namespace std;
// 二维数组matrix中,每一行都从左到右递增排序,
// 每一列都从上到下递增排序
bool Find(int* matrix, int rows, int columns, int number)
{
bool found = false;
if(matrix != NULL && rows > 0 && columns > 0)
{
int row = 0;
int column = columns - 1;
while(row < rows && column >=0)
{
if(matrix[row * columns + column] == number)
{
found = true;
break;
}
else if(matrix[row * columns + column] > number)
-- column;
else
++ row;
}
}
return found;
}
void Test(char* testName, int* matrix, int rows, int columns, int number)
{
if(testName != NULL)
printf("%s begins: ", testName);
bool result = Find(matrix, rows, columns, number);
if(result == true)
printf("Passed.\n");
else
printf("Failed.\n");
}
// 要查找的数在数组中
void Test1()
{
int matrix[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
Test("Test1", (int*)matrix, 4, 4, 7);
}
// 要查找的数不在数组中
void Test2()
{
int matrix[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
Test("Test2", (int*)matrix, 4, 4, 5);
}
int main(int argc, char * argv[])
{
Test1();
Test2();
return 0;
}