算法刷题目数组和矩阵
Source
Edit
History

在行列都排好序的矩阵中找指定值

在行列都排好序的矩阵中找指定值

一、题目

在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

现有矩阵 matrix 如下：

1
2
3
4
5
6
7
[
  [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。

给定 target = 20，返回 false。

Leetcode：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

二、思路

本题目思路很简单，要么从右上角的坐标开始寻找：

  • 如果此坐标的值为 target，则找到了，返回 true
  • 如果此坐标的值大于 target，则应该让列减减，因为列是非递减的顺序排好序的。
  • 如果此坐标的值大于 target，则应该让行加加，因为行也是非递减的顺序排好序的

要么从左下角的坐标开始寻找，思路同上。

就是不能从左上角或者右下角找，因为假如当前元素大于或者小于 target 了，都不知道按行走，还是按列走了。而且硬走的话，时间复杂度变为了 O(m*n)。而我们需要的时间复杂度为 O(m+n)

三、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <vector>
#include <iostream>

class Solution {
public:
    bool findNumberIn2DArray(const std::vector<std::vector<int>>& matrix, int target) {
        if (matrix.empty()) {
            return false;
        }
        // 从右上角开始找
        int row = 0, line = matrix[0].size() - 1;
        for (; row < matrix.size() && line >= 0;) {
            int val = matrix[row][line];
            if (val == target) {
                return true;
            } else if (val > target) {
                line--;
            } else if (val < target) {
                row++;
            }
        }
        return false;
    }
};

int main() {
    std::vector<std::vector<int>> matrix{{0, 1, 2, 5}, {2, 3, 4, 7}, {4, 4, 4, 8}, {5, 7, 7, 9}};
    Solution s;
    auto res = s.findNumberIn2DArray(matrix, 6);
    std::cout << (res ? "true" : "false") << std::endl;
}