矩阵

搜索二维矩阵 II

中等#240Java时间 O(m+n)空间 O(1)

题目要做什么

矩阵每行从左到右递增,每列从上到下递增,判断目标值是否存在。整体按行展开未必有序。

题目示例输入matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16]], target = 5
题目示例输出true

01 为什么这样做

从右上角开始。当前值大于目标时,整列下方更大,可向左淘汰该列;当前值小于目标时,整行左侧更小,可向下淘汰该行。

始终成立的条件

目标若存在,始终位于当前行以下、当前列左侧的候选矩形中。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public boolean searchMatrix(int[][] matrix, int target) {3        int row = 0, col = matrix[0].length - 1;4        while (row < matrix.length && col >= 0) {5            int value = matrix[row][col];6            if (value == target) return true;7            if (value > target) col--;8            else row++;9        }10        return false;11    }12}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索