题解 | #ZJ1二维数组中的查找#

二维数组中的查找

这是剑指Offer的第一道题目。 2星难度。

要利用好每行每列元素有序这个点。

思路很重要，暴力解法不可取。O(m*n)

而通过借鉴类似图片放大缩小的手法，可以将最大复杂度降到O(m+n)
我为这种方法起了一个名字： 【对角元素限制法】

见名之意，日后遇见类似二维数组中查找的题目，可借鉴对角元素限制法。

public class Solution {
    public boolean Find(int target, int [][] array) {
//做好特殊情况的处理是所有题解的第一步。
        int m=array.length;
        if (m==0) return false;
        int n=array[0].length;
        if(n==0) return false;
//二维数组中，r是行，c是列。
        int r=0,c=n-1;
        while(r<m&&c>=0){
            if(target==array[r][c]) return true;
//通过对二维图像角的拉缩来进行候选集的过滤。
            if(target>array[r][c]) {
                r++;
            }else c--;
        }
    return false;
    }
}