By

题目描述

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

题目解析

这一题一开始我直接用C#进行遍历搜索，严格来说这也不能算是一种解题方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution
{
    public bool Find(int[][] array, int target)
    {
        foreach(int[] a in array)
        {
            foreach(int b in a)
            {
                if(b==target)
                {
                    return true;
                }
            }
        }
        return false;
    }
}

实际上，题目给出的二维数组每一行从左到右递增，每一列从上到下递增。我们可以从左下角开始比较，若左下角的数小于target，则往右遍历；若左下角的数大于target，则往上遍历。这样可以最快地找出target。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        int height=array.size();
        int width=array[0].size();
         
        for(int i=height-1,j=0;i>=0&&j<width;){
                if(target>array[i][j])
                    j++;
                else if(target<array[i][j])
                    i--;
                else return true;
        }
        return false;
    }
};