LeetCode 240.搜索二维矩阵II(中等)

题目描述:

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

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

示例 1:

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2:

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示:

• ​​m == matrix.length​​
• ​​n == matrix[i].length​​
• ​​1 <= n, m <= 300​​
• - <= matrix[i][j] <=
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• - <= target <=

题目分析:

这道题有一个很巧妙的技巧，你可以通过仔细观察就能发现其中的奥秘。特别注意左下角元素或者右上角元素与其他元素的关系。你可以从右上角开始查找，若当前值大于目标值，你就向左移动一格；若当前值小于目标值，你就向下移动一格。如果最终移动到左下角时仍不等于目标值，则说明目标值不存在于矩阵中。或者你可以从左下角开始查找，若当前值大于目标值，你就向右移动一格；若当前值小于目标值，你就向上移动一格。如果最终移动到右上角时仍不等于目标值，则说明目标值不存在于矩阵中。

题解:

执行用时: 5 ms

内存消耗: 44 MB

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 获取矩阵行数
        int row = matrix.length;
        // 行数为 0 即没有矩阵，直接返回 false
        if (row == 0) {
            return false;
        }
        // 获取矩阵列数
        int column = matrix[0].length;
        // 查找索引
        int i = 0, j = column - 1;
        // 当行数索引和列数索引没有越界时循环查找
        while (i < row && j >= 0) {
            // 当前元素刚好为目标元素，返回 true
            if (target == matrix[i][j]) {
                return true;
            } else if (target < matrix[i][j]) {
                // 如果目标值小于当前元素，向左查找
                --j;
            } else {
                // 否则目标值大于当前元素，向下查找
                ++i;
            }
        }
        // 没有找到目标元素返回 false
        return false;
    }
}

题目来源:力扣(LeetCode)