Hot100 - 搜索二维矩阵II
最佳思路：
利用矩阵的特性，针对搜索操作可以从右上角或者左下角开始。通过判断当前位置的元素与目标值的关系，逐步缩小搜索范围，从而达到较高的效率。
- 从右上角开始：假设矩阵是升序排列的（每行和每列都升序）。如果当前位置的元素等于目标值，返回
true；如果当前位置的元素小于目标值，向下移动（行索引加 1）；如果当前位置的元素大于目标值，向左移动（列索引减 1）。通过这种方式，可以快速排除不可能的部分。
时间复杂度：
- 时间复杂度为 O(m+n)O(m + n)，其中 mm 是矩阵的行数，nn 是矩阵的列数。在最坏情况下，最多需要检查一行和一列的元素。
思路解析：
- 从右上角开始搜索：矩阵的每一行是升序排列的，每一列也是升序排列的。从右上角元素开始，如果当前元素等于目标值，返回
true；如果小于目标值，则说明当前元素及其所在的列不可能包含目标值，向下移动；如果大于目标值，则说明当前元素及其所在的行不可能包含目标值，向左移动。 - 逐步缩小搜索范围：通过不断调整行列索引，逐步缩小可能包含目标值的区域，直到找到目标值或确定目标值不存在。
代码实现：
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length; // 行数int n = matrix[0].length; // 列数int i = 0; // 从第一行开始int j = n - 1; // 从最后一列开始while (i < m && j >= 0) {if (matrix[i][j] == target) {return true; // 找到目标值} else if (matrix[i][j] < target) {i++; // 向下移动} else {j--; // 向左移动}}return false; // 没有找到目标值}
}
思路总结：
- 优化搜索：通过从矩阵的右上角开始搜索，可以利用矩阵的行列升序特点，有效缩小搜索范围。
- 时间复杂度：在最坏情况下，我们最多会搜索 m+nm + n 次元素，比直接遍历整个矩阵的 O(m×n)O(m \times n) 要高效得多。
- 空间复杂度：此方法使用了常数空间 O(1)O(1)，不需要额外的空间来存储数据。
