当前位置：首页 > article >正文

【LeetCode】【算法】240. 搜索二维矩阵II

article 2024/11/13 20:30:45

LeetCode 240. 搜索二维矩阵II

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

思路

思路：K神真强啊240.搜索二维矩阵II（贪心，清晰图解）

K神的思路实际上就是将矩阵转45°，将矩阵最下边的值作为flag，不断判断flag与target的关系，不断贪心地进行移动，直到找到target值或者flag移动到target为止。因为数组严格满足从左到右升序、从上到下升序的性质，我自己写时候的想法就是通过一堆if-else语句来挪动指针，非常低效，而且超时了（我没有在本地验证自己的代码，不清楚正确性）
逆时针旋转45度之后，满足这样一种情况：
假如flag>target，则target一定在flag所在行的上方，即flag在原矩阵中的 “行”可以被消除（j++）
假如flag<target，则target一定在flag所在列的右方，即flag在原矩阵中的“列”可以被消除（i–）
通过这样的形式对flag进行一个缩放

代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] > target) i--;
            else if (matrix[i][j] < target) j++;
            else return true; // ==的情况
        }
        return false;
    }
}

自己写的垃圾。。。

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