剑指Offer04:二维数组中的查找

剑指 Offer 04. 二维数组中的查找 - 力扣（Leetcode）

解题思路：

若使用暴力法遍历矩阵 matrix ，则时间复杂度为 O(NM) 。暴力法未利用矩阵 “从上到下递增、从左到右递增” 的特点，显然不是最优解法。

这道题我首先想到的就是暴力解法,时间复杂度最大：

public boolean findNumberIn2DArray(int[][] matrix, int target) {
       for(int [] list : matrix){
           for(int n : list){
                if(n == target)return true;

                }
           }
        return false;
}

当然有更好的解法，比如说，我们利用题目中二维数组每行递增的特点，每行都进行二分查找。这种方法的时间复杂度为O(mlogn)，因为每次二分的时间复杂度为logn.

遍历二维数组的每一行，调用二分查找方法：

public boolean findNumberIn2DArray(int[][] matrix, int target) {

        boolean result = false;
        for(int list[]:matrix){
            result = binarySearch(list,target);
            if(result==true)return true;
        }
        return false;

    }
    public boolean binarySearch(int[] list, int target){
        int low = 0,high = list.length-1;
        while(low<=high){
            int mid = (high - low) / 2 + low;
            if(list[mid]<target)low = mid+1;
            else if(list[mid]>target)high = mid - 1;
            else return true;

        }
        return false;
    }    

巧妙方法：如下图所示，我们将矩阵逆时针旋转 45° ，并将其转化为图形式，发现其类似于 二叉搜索树 ，即对于每个元素，其左分支元素更小、右分支元素更大。因此，通过从 “根节点” 开始搜索，遇到比 target 大的元素就向左，反之向右，即可找到目标值 target 。

剑指 Offer 04. 二维数组中的查找 - 力扣（Leetcode）

根节点” 对应的是矩阵的 “左下角” 和 “右上角” 元素，本文称之为 标志数 ，以 matrix 中的 左下角元素 为标志数 flag ，则有:

若 flag > target ，则 target 一定在 flag 所在 行的上方 ，即 flag 所在行可被消去。
若 flag < target ，则 target 一定在 flag 所在 列的右方 ，即 flag 所在列可被消去。
算法流程：

1. 从矩阵 matrix 左下角元素（索引设为 (i, j) ）开始遍历，并与目标值对比：
   当 matrix[i][j] > target 时，执行 i– ，即消去第 i 行元素；
   当 matrix[i][j] < target 时，执行 j++ ，即消去第 j 列元素；
   当 matrix[i][j] = target 时，返回 truetruetrue ，代表找到目标值。

2. 若行索引或列索引越界，则代表矩阵中无目标值，返回 falsefalse 。

当然，我们这里也可以采用另外一种遍历方法，即从矩阵的右上角开始自上而下遍历，

• 若 flag > target ，则 target 一定在 flag 所在 行的下方 ，即 flag 所在行可被消去，执行i++；

• 若 flag < target ，则 target 一定在 flag 所在 列的左方 ，即 flag 所在列可被消去，执行j–；

• 若行索引或列索引越界，则代表矩阵中无目标值，返回false 。

  代码如下：

public boolean findNumberIn2DArray(int[][] matrix, int target) {

        if(matrix.length==0)return false;
        int i = 0,j = matrix[0].length-1;
        while(j>=0 && i<matrix.length){
            if(matrix[i][j]<target)i++;
            else if(matrix[i][j]>target)j--;
            else return true;
        }
        return false;


}