240. 搜索二维矩阵 II

题目链接：https://leetcode.cn/problems/search-a-2d-matrix-ii/

代码

function searchMatrix(matrix: number[][], target: number): boolean {
    let i = 0;
    let j = matrix[0].length - 1;
    while (i <= matrix.length - 1 && j >= 0) {
        if (target === matrix[i][j]) return true;
        else if (target < matrix[i][j]) {
            j--;
        }
        else {
            i++;
        }
    }
    return false;
};

思路

利用矩阵的特性（每行从左到右递增，每列从上到下递增），从右上角开始搜索：

1. 初始化指针 i = 0（第一行），j = matrix[0].length - 1（最后一列）
2. 比较当前元素 matrix[i][j] 与目标值 target：
   • 如果相等，返回 true
   • 如果当前元素大于目标值，说明这一列的所有元素都大于目标值，向左移动：j--
   • 如果当前元素小于目标值，说明这一行的所有元素都小于目标值，向下移动：i++
3. 如果指针越界还没找到，返回 false

这个算法的关键是选择从右上角（或左下角）开始，这样每次比较都能排除一行或一列。

• 时间复杂度 $O(m+n)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数
• 空间复杂度 $O(1)$