搜索二维矩阵 II
难度:
标签:
题目描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
输入：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]], target = 5 输出：true
示例 2：
输入：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]], target = 20 输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
-109 <= target <= 109
代码结果
运行时间: 120 ms, 内存: 22.1 MB
/*
* 思路：
* 使用Stream API逐行过滤，并在每行中检查是否包含目标值。
* 从右上角开始，如果找到目标值返回true，否则继续搜索。
*/
import java.util.Arrays;
import java.util.Optional;
public class SolutionStream {
public boolean searchMatrix(int[][] matrix, int target) {
return Arrays.stream(matrix)
.anyMatch(row -> Arrays.binarySearch(row, target) >= 0);
}
}
解释
方法:
这个题解采用了一种巧妙的搜索方式。从矩阵的右上角开始搜索，如果当前元素等于目标值，则找到目标值，直接返回 true。如果当前元素大于目标值，由于当前元素已经是该列最小的元素，因此将搜索范围缩小到当前元素的左边一列。如果当前元素小于目标值，由于当前元素已经是该行最大的元素，因此将搜索范围缩小到当前元素的下面一行。通过不断缩小搜索范围，最终可以确定目标值是否存在于矩阵中。
时间复杂度:
O(m+n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择从矩阵的右上角开始搜索而不是其他角，比如左上角或右下角？
▷🦆
在算法中，如果当前元素大于目标值，为什么可以确定缩小搜索范围到当前元素的左边一列而不查看下方的元素？
▷🦆
当当前元素小于目标值时，算法中提到将搜索范围缩小到下一行，这是否暗示矩阵的每列也是严格递增的？
▷🦆
如果矩阵为一个空矩阵，或者某些行或列为空，该算法是否还能正确运行？
▷相关问题
搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104