剑指Offer - 二维数组中的查找(Java实现)

题目链接：https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&&tqId=11154&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一： 暴力查找(O(nm)):直接遍历二维数组查找即可。

public class Solution {
    public boolean Find(int target, int [][] array) {
        int n = array.length, m = array[0].length;
        for(int i = 0; i < n; ++ i) {
            for(int j = 0; j < m; ++ j) {
                if(target == array[i][j]) return true;
            }
        }
        return false;
    }
}

  思路二：遍历行O(nlog(m)):我们遍历每一行,由于每一行都是一个有序的数组,在当前行我们使用二分查找判断是否包含target

public class Solution {
    public boolean Find(int target, int [][] array) {
        int n = array.length, m = array[0].length;
        for(int i = 0; i < n; ++ i) {
            int l = 0, r = m - 1;
            while(l <= r) {
                int mid = (l + r) >> 1;
                if(array[i][mid] < target) l = mid + 1;
                else if(array[i][mid] > target) r = mid - 1;
                else return true;
            }
        }
        return false;
    }
}

  思路三：遍历列O(mlog(n))

public class Solution {
    public boolean Find(int target, int [][] array) {
        int n = array.length, m = array[0].length;
        for(int j = 0; j < m; ++ j) {
            int l = 0, r = n - 1;
            while(l <= r) {
                int mid = (l + r) >> 1;
                if(array[mid][j] < target) l = mid + 1;
                else if(array[mid][j] > target) r = mid - 1;
                else return true;
            }
        }
        return false;
    }
}

  思路四：思维O(m+n):我们可以发现，如果当前我们要判断的数字在右上方，如果这个数大于目标数字，那么目标数字就在其左边，如果小于目标数字，那么目标数字就在其下边，由于二维数组是有序的，所以一旦我们移动了位置以后，后面我们动的方向就只能是左边或者下边，这样一来到达边界时如果我们找到了就返回 ,否则就返回 。如果当前我们判断的数字位于左下方，那么同理下一步我们只能向上或者向右走。

//右上方
public class Solution {
    public boolean Find(int target, int [][] array) {
        int n = array.length;
        if(n == 0) return false;
        int m = array[0].length;
        if(m == 0) return false;
        int row = 0, cow = m - 1;
        while(row < n && cow >= 0) {
            if(array[row][cow] > target) -- cow;
            else if(array[row][cow] < target) ++ row;
            else return true;
        }
        return false;
        /*5,[
            [1,2,8,9],
            [2,4,9,12],
            [4,7,10,13],
            [6,8,11,15]
        ]*/
    }
}

//左下方
public class Solution {
    public boolean Find(int target, int [][] array) {
        int n = array.length;
        if(n == 0) return false;
        int m = array[0].length;
        if(m == 0) return false;
        int row = n - 1, cow = 0;
        while(row >= 0 && cow < m) {
            if(array[row][cow] > target) -- row;
            else if(array[row][cow] < target) ++ cow;
            else return true;
        }
        return false;
        /*5,[
            [1,2,8,9],
            [2,4,9,12],
            [4,7,10,13],
            [6,8,11,15]
        ]*/
    }
}