【算法】二维数组中的查找
题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
最开始有一个崎岖的想法：
那就是根据向右递增，向下递增这个法则，从最后一个数开始往前数，以及往上数，来确定目标数的范围，再去找这个数，结果就是很费劲：
简直是费了老大的劲，其实没那么麻烦：
想想，只要先把指针放在右上角这个数，来跟目标数比较，等于的话，直接返回真；小于的话，把指针往下移动；大于的话，把指针往左移动，直到找到目标数，或者指针移到左下角了，仍未找到，那就返回 false:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int i=0;
int t=0;
int indexX=array.size()-1;
int indexY=array[0].size()-1;
for (i=0,t=indexY;i<=indexX&&t>=0;)
{
if (array[i][t]==target)
return true;
else if(array[i][t]>target)
{
t--;
continue;
}
else
{
i++;
continue;
}
}
return false;
}
}; |
一大教训就是，写算法题，要好好考虑下思路，一定要找到最优解题思路，再动手！不然会白费很多力气。