【剑指offer】二维数组中的查找

题意：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

题解：这道题最容易想到的是o(n*m)的算法。[顺便BB一句，我参加17年的牛客的Google girl的面试时，面试官就出了这个题。] 回看一下题目的条件，就会发现这个数组是一个很特殊的数组。

1 2 3

4 5 6

7 8 9

取一个比较极端的例子，可以看出来，左上角永远是最小数，右下角永远是最大数。我们把目标值定为target，以副对角线划分，可以看出来小的在左边，大的在右边。也就是我们从右上角开始，如果target < a[i][j],那么j--,如果target > a[i][j],那么i++.这样出来的复杂度就o(m+n)了。

代码：

java

 1 public class Solution {
 2     public boolean Find(int target, int [][] array) {
 3         int col = array[0].length-1;
 4         int row = 0;
 5         while(col>=0 && row < array.length){
 6             if(array[row][col] == target){
 7                 return true;
 8             }
 9             else if(array[row][col] > target){
10                 col--;
11             }
12             else{
13                 row++;
14             }
15         }
16         return false;
17     }
18 }

c++

 1 class Solution {
 2 public:
 3     bool Find(int target, vector<vector<int> > array) {
 4         int len = array[0].size();
 5         int col = len - 1;
 6         int row = 0;
 7         while(col >= 0 && row < len){
 8             if(array[row][col] == target){
 9                 return true;
10             }
11             else if(array[row][col] < target){
12                 row++;
13             }
14             else{
15                 col--;
16             }
17         }
18         
19         return false;
20     }
21 };