菠萝菠萝卜的博客

力扣每日一题 2021/10/25

  • 2021-10-25
  • 作者 菠萝菠萝卜
  • 1122 字
  • 次阅读
  1. 1. 240.搜索二维矩阵II
  2. 2. 解题思路
  3. 3. 解题代码

240.搜索二维矩阵II

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

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

示例 1：

1
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 = 5
输出：true

示例 2：

1
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
  • -109 <= matrix[i][j]<= 109
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -109 <= target <= 109

原文链接

解题思路

遍历每一行的最大值，也就是最右边的一列，如果这一行最大的值都比target小，那说明不存在，直接跳到下一行，直到最大值大于target，然后继续从右往左找到target，如果没有说明没有该值。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
     if(matrix.length == 0) {
            return false;
        }
        int i = 0;
        int j = matrix[0].length-1;
        while(i < matrix.length && j >= 0) {
            if(matrix[i][j] == target) {
                return true;
            }
            if(matrix[i][j] < target) {
                ++i;
            }
            else {
                --j;
            }
        }
        return false;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2021-10-25