时间轴

2026-03-13

init

题目：

P240 搜索二维矩阵 II

https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked

最开始我是这样想的：

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <vector>
using std::vector;

class Solution {
    private:
        int binary_search_column(vector<vector<int> > &matrix, int target, int column)
        {
                // 按列二分搜索
                // 1 <= n, m <= 300
                int m = matrix.size();
                int left = 0, right = m - 1, mid;

                while (left < right) {
                        mid = (left + right) / 2;
                        if (matrix[mid][column] > target) {
                                right = mid - 1;
                        } else if (matrix[mid][column] < target) {
                                left = mid + 1;
                        } else {
                                return mid;
                        }
                }
                // if not found it should return greatest value that < target
                if (matrix[left][column] <= target)
                        return left;
                else
                        return left == 0 ? 0 : left - 1;
        }
        int binary_search_row(vector<vector<int> > &matrix, int target, int row)
        {
                // 按行二分搜索
                int n = matrix[0].size();
                int left = 0, right = n - 1, mid;

                while (left < right) {
                        mid = (left + right) / 2;
                        if (matrix[row][mid] > target) {
                                right = mid - 1;
                        } else if (matrix[row][mid] < target) {
                                left = mid + 1;
                        } else {
                                return mid;
                        }
                }
                if (matrix[row][left] <= target)
                        return left;
                else
                        return left == 0 ? 0 : left - 1;
        }

    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target)
        {
                // 1 <= n, m <= 300
                int row, column;
                // 第一行
                column = binary_search_row(matrix, target, 0);
                if (matrix[0][column] == target)
                        return true;
                row = binary_search_column(matrix, target, column);
                if (matrix[row][column] == target)
                        return true;

                // 第一列
                row = binary_search_column(matrix, target, 0);
                if (matrix[row][0] == target)
                        return true;

                column = binary_search_row(matrix, target, row);
                if (matrix[row][column] == target)
                        return true;

                return false;
        }
};

int main()
{
        Solution S;
        // vector<vector<int> > 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 } };

        // vector<vector<int> > matrix = { { 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 } };

        vector<vector<int> > matrix = { { 1, 3, 5, 7, 9 },
                                        { 2, 4, 6, 8, 10 },
                                        { 11, 13, 15, 17, 19 },
                                        { 12, 14, 16, 18, 20 },
                                        { 21, 22, 23, 24, 25 } };

        // int target = 5;
        // int target = 19;

        int target = 13;
        S.searchMatrix(matrix, target);
}

但明显第三个测试用例是无法找到target的。

而实际上我们应该从右上角开始查找：

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <vector>
using std::vector;

class Solution {
    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target)
        {
                // 1 <= n, m <= 300
                int m = matrix.size(), n = matrix[0].size();
                int row = 0, column = n - 1;

                // 从右上角开始搜索
                while (row >= 0 && row < m && column >= 0 && column < n) {
                        if (matrix[row][column] < target) {
                                row++;
                        } else if (matrix[row][column] > target) {
                                column--;
                        } else {
                                return true;
                        }
                }

                return false;
        }
};

int main()
{
        Solution S;
        // vector<vector<int> > 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 } };

        // vector<vector<int> > matrix = { { 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 } };

        vector<vector<int> > matrix = { { 1, 3, 5, 7, 9 },
                                        { 2, 4, 6, 8, 10 },
                                        { 11, 13, 15, 17, 19 },
                                        { 12, 14, 16, 18, 20 },
                                        { 21, 22, 23, 24, 25 } };

        // int target = 5;
        // int target = 19;

        int target = 13;
        S.searchMatrix(matrix, target);
}