74. 搜索二维矩阵

1、题目描述

2、题目分析：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

2-1、【暴力法】整理题目思路

1、可以知道坐标在[0][0]点的元素，一定是最小元素，如果等于matrix[0][0] , 则返回true, 如果(target < matrix[0][0]), 即比矩阵中最小值还小， 则返回false

2、接下来遍历每一行第一个元素，即matrix[i][0], 如果等于某一行第一个元素，返回true, 如果matrix[i][0] > target, 则终止此次循环，跳出。

3、此时可以得到目标行下标

4、同理在对应行遍历每一列元素，如果有相等的则返回true, 否则为false.

 这个逻辑比较好想，但是没啥巧妙之处，实现代码如下：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0)   
            return false;
        int row = matrix.length;
        int col = matrix[0].length;
        //初始校验
        int minNum = matrix[0][0];
        if(target == minNum) return true;
        else if(target < minNum) return false;

        int aimRow = 1;
        //遍历每一行第一个元素，确定目标值在哪一行
        for(; aimRow < row; aimRow++){
           int rowNum = matrix[aimRow][0];
           if(rowNum == target) return true;
           else if (rowNum > target) break;      
        }
        //此时确定了所在行的下标,比所在行的最大值还大，则也不存在目标值
        aimRow--;
        if(target > matrix[aimRow][col-1])
            return false;
        
        //遍历目标行的每一列
        for(int j = 1; j < col; j++){
           int colNum = matrix[aimRow][j];
           if(colNum == target) return true;
        }
        return false;
    }
}

复杂度分析

时间复杂度：O(n+m), 其中 m 和 n 分别是矩阵的行数和列数。

空间复杂度：O(1)。

2-2、针对以上思路，进行代码优化

上面题目的解题思路其实就是坐标轴并进行比较大小逻辑。同时进行，【行】+【列】遍历.

根据题意已知，二维数组从左往右递增，从上往下递增，所以得出以下结论：

某列的某个数字，该数之上的数字，都比其小；
某行的某个数字，该数右侧的数字，都比其大；
所以，解题流程如下所示：

以二维数组左下角为原点，建立直角坐标轴。
若当前数字大于了查找数，查找往上移一位。
若当前数字小于了查找数，查找往右移一位。

代码写法如下：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //从【左下角】开始遍历，如果target < 当前值 ，rows--, 如果 target>当前值，col++
        int rows = matrix.length - 1, columns = 0;
        while (rows >= 0 && columns < matrix[0].length) {
            int num = matrix[rows][columns];
            if (num == target) {
                return true;
            } else if (num > target) {
                rows--;
            } else {
                columns++;
            }
        }
        return false;
    }
}

复杂度分析

时间复杂度：O(n+m), 其中 m 和 n 分别是矩阵的行数和列数。

空间复杂度：O(1)。

其他：还可以根据官方思路，进行二分查找等思路。