search2dMatrixII

240. 搜索二维矩阵II

分析

利用矩阵的排序特性，可以从矩阵的右上角（或左下角）开始搜索：

选择右上角 (0, m - 1) 为起点：
- 如果当前位置的值等于目标值，返回 true
- 如果当前位置的值小于目标值，则向下移动一行（增加行索引）
- 如果当前位置的值大于目标值，则向左移动一列（减少列索引）
退出条件：
- 如果行索引越界 x > n 或列索引越界 y < 0，说明矩阵中没有目标值，返回 false

时间复杂度

每次移动都会排除当前行或列的一部分，最多移动 m + n 次，因此时间复杂度为 O(m + n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution
{
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target)
    {
        int n = matrix.size(), m = matrix[0].size();
        if (n == 0 || m == 0) return false;

        int x = 0, y = m - 1; // 从右上角开始
        while (x < n && y >= 0)
        {
            if (matrix[x][y] == target)
                return true; // 找到目标值
            else if (matrix[x][y] < target)
                ++ x; // 目标值更大，向下移动
            else
                -- y; // 目标值更小，向左移动
        }
        return false; // 未找到目标值
    }
};