排序矩阵查找
难度:
标签:
题目描述
Given an M x N matrix in which each row and each column is sorted in ascending order, write a method to find an element.
Example:
Given 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] ]
Given target = 5, return true.
Given target = 20, return false.
代码结果
运行时间: 26 ms, 内存: 20.4 MB
/**
* Given an MxN matrix where each row and each column is sorted in ascending order,
* write a code to find a specific element using Java Streams.
*
* Approach:
* We can use the same logic as above but filter rows and columns with Streams.
* We can flatten the 2D matrix into a stream and check for the target using anyMatch.
*/
import java.util.Arrays;
public class MatrixSearchStream {
public boolean searchMatrix(int[][] matrix, int target) {
return Arrays.stream(matrix)
.flatMapToInt(Arrays::stream)
.anyMatch(x -> x == target);
}
}解释
方法:
该题解采用的是逐行扫描的方法。首先，检查矩阵是否为空。对于每一行，如果该行的最后一个元素大于或等于目标值，则在该行中逐个检查元素是否等于目标值。这种方法是基于每行和每列都是升序的事实，如果某行的最后一个元素已经小于目标值，那么目标值不可能出现在当前行或之前的行中。
时间复杂度:
O(MN)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么逐行扫描选择检查行的最后一个元素而不是第一个元素来决定是否在该行继续查找？
▷🦆
如果矩阵的行数远大于列数，或者列数远大于行数，这种方法的效率如何？是否有更优的搜索方法？
▷🦆
代码中的`if len(matrix)==0 or len(matrix[0])==0`检查是为了处理什么特殊情况？能否给出一个具体的例子？
▷