剑指 Offer 04. 二维数组中的查找

题目地址：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

题目的主要信息：

• 二维数组array中，每个一维数组的长度均相同。
• 每一行都按照从左到右递增的顺序排序。
• 每一列都按照从上到下递增的顺序排序。

提示：必须将题目的信息都用上，才能写出最优解。

一、暴力解法（双层for循环）

对于二维数组 int[][] array = new int[m][n];

• 获取二维数组的行数(m)：int row = array.length;
• 获取二维数组的列数(n)：int column = array[0].length;

解题思路：

• 使用双层for循环，外层遍历二维数组的行，内层遍历二维数组的列，将数组中的每一个元素都与target目标元素比较。

public class Solution {

    public static void main(String[] args) {
        int[][] array = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        System.out.println(new Solution().findNumberIn2DArray(array, 3));
    }

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 优先处理特殊情况
        if(matrix.length == 0) return false;

        // 外层循环遍历二维数组的行
        for(int i = 0; i < matrix.length; i++){
            // 内层循环遍历二维数组的列
            for(int j = 0; j < matrix[0].length; j++){
                // 如果数组中存在目标元素，直接返回true
                if(matrix[i][j] == target) return true;
            }
        }
        
        return false;
    }

}

复杂度分析：

• 时间复杂度是：$O(mn)$。遍历数组行的时间复杂度是$O(m)$，遍历数组列的时间复杂度是$O(n)$，因此总体时间复杂度是 $O(m\ast n)$ = $O(mn)$

• 空间复杂度是：$O(1)$。常量级变量，无额外辅助空间。

分析：强烈不建议这种做法，当一个算法的时间复杂度为 $O(n^2)$ 时，你就该考虑优化它了

二、二分查找

解题思路：

• 遍历二维数组的行。

• 由于数组的每一行都按照从左到右递增的顺序排序，所以可以使用二分查找。

public class Solution {

    public static void main(String[] args) {
        int[][] array = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        System.out.println(new Solution().findNumberIn2DArray(array, 2));
    }

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 优先处理特殊情况
        if (matrix.length == 0) return false;

        // 遍历二维数组的行, 时间复杂度为O(m)
        for (int i = 0; i < matrix.length; i++) {
            // 每行从左往右都是升序的，所以对行的查找可以使用二分查找，时间复杂度为O(logn)
            int left = 0, right = matrix[0].length - 1;  // 左右指针
            while (left <= right) {
                int mid = (right + left) / 2;
                if (target == matrix[i][mid]) {
                    return true;
                } else if (target > matrix[i][mid]) {
                    left = mid + 1;
                }else if(target < matrix[i][mid]){
                    right = mid - 1;
                }
            }
        }

        return false;
    }

}

复杂度分析：

• 时间复杂度是：$O(mlogn)$。for循环遍历二维数组的行的时间复杂度是$O(m)$，for循环体中使用了二分查找的时间复杂度是$O(logn)$，因此总体时间复杂度是 $O(m\ast logn)$ = $O(mlogn)$

• 空间复杂度是：$O(1)$。常数级变量，无额外辅助空间

分析：如果题目中没有 每一列都按照从上到下递增的顺序排序 这个信息，那么这种做法就是最优解了。但这个信息没用上，显然就不会是最优解。

三、左下角坐标法（推荐）

解题思路：

1. 传入的二维数组中，每一行都按照从左到右递增的顺序排序，每一列也都按照从上到下递增的顺序排序。

2. 所以二维数组左下角的元素，比它上边的元素大，比它右边的元素小。

3. 根据左下角元素的这一规律，可以将二位数组划分成一个大区域和一个个小区域。每次将目标元素与左下角元素比较，我们就可以直到目标元素应该在哪一个区域中，从而缩小比较范围，较少比较次数。 ( 分治思维 )

具体做法：

• step 1：首先获取矩阵的两个边长，判断特殊情况。
• step 2：首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。
• step 3：若是移动到了矩阵边界也没找到，说明矩阵中不存在目标值。

public class Solution {

    public static void main(String[] args) {
        int[][] array = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        System.out.println(new Solution().findNumberIn2DArray(array, 2));
    }

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 优先处理特殊情况
        if (matrix.length == 0) return false;
        
        // 二维数组左下角元素的下标
        int row = matrix.length - 1;
        int column = 0;
        while (row >= 0 && column < matrix[0].length) {
            if (target == matrix[row][column]) {
                return true;
            } else if (target < matrix[row][column]) {
                row--;
            } else if (target > matrix[row][column]) {
                column++;
            }
        }

        return false;
    }

}

复杂度分析：

• 时间复杂度 $O(m+n)$。最坏的情况是目标元素在二维数组的右上角 ( 或者数组中没有目标元素 )，即遍历二维数组的时候，最多经过二维数组的一行一列，所以总体时间复杂度为$O(m+n)$。

• 空间复杂度 $O(1)$。常数级变量，无额外辅助空间。