1.题目
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
2.思路
假设选定一个要查找的数字，如果在数组中任意选取一个数字来和该数字作比较，可能会导致下一次要查找的区域发生重叠。为了简化查找过程，我们可以选取每个查找区域右上角数据（左下角数据也可，原理相同）和要查找的数字进行比较。此时只会发生三种情况：
- 右上角的数字等于要查找的数字。查找过程结束。
- 右上角的数字大于要查找的数字。根据该二维数组的特征，排除右上角数字所在的列。
- 右上角的数字小于要查找的数字。同理，排除右上角数字所在的行。
重复以上1~3步，如果要查找的数字不在所查找区域的右上角，那么就每一次都排除一行或者一列，逐渐缩小查找范围，直到找到要查找的数字，或者查找结果为空。
3.举例说明
4.代码实现
c++：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int rows = array.size();//数组的行序号
int cols = array[0].size();//数组的列序号
if(!array.empty() && rows > 0 && cols > 0){//若数组内容非空、行列序号均大于零
int row = 0;
int col = cols - 1;//右上角数据的行、列序号
while(row < rows && col >= 0){//当右上角数据存在时
if(array[row][col] == target){
return true;//若两数相同，查找结束
}
else if(array[row][col] > target){//若右上角数字大于被查找数，行不变，列减少
--col;
}
else{
++row;//若右上角数字小于被查找数，行增加，列不变
}
}
}
return false;//否则，数组中不存在被查找数，查找失败
}
};
|
python2.7：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| # -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
rows = len(array)
cols = len(array[0])
if rows > 0 and cols > 0:
row = 0
col = cols - 1
while row < rows and col >= 0:
if target == array[row][col]:
return True
elif target < array[row][col]:
col -= 1
else:
row += 1
return False
|