寻找目标值 - 二维数组
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 40 ms, 内存: 17.3 MB
/*
* 思路:
* 尽管 Java Stream 不直接支持二维数组的处理,但我们可以将二维数组转换为一维流进行处理。
* 将二维数组中的每个元素放入一个 List,然后利用 Stream API 进行查找。
*/
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class Solution {
public boolean searchMatrix(int[][] plants, int target) {
List<Integer> list = Arrays.stream(plants)
.flatMapToInt(Arrays::stream)
.boxed()
.collect(Collectors.toList());
return list.contains(target);
}
}
解释
方法:
该题解采用从右上角开始搜索的方法来查找目标值。考虑二维数组的每一行从左到右递增,每一列从上到下递增的特性,可以将右上角元素视作一个分水岭:如果目标值小于该元素,则目标不可能出现在当前元素的所在列(因为下方的元素都比当前元素大),因此向左移动;如果目标值大于该元素,则目标不可能出现在当前元素的所在行(因为左侧的元素都比当前元素小),因此向下移动。这样逐步缩小搜索范围,直到找到目标值或者确认目标值不存在。
时间复杂度:
O(m+n)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中,你是如何确定从右上角开始搜索的初始位置,而不是其他角落的元素?
▷🦆
如果目标值等于右上角的元素,搜索过程是否会立即终止,还是会继续搜索整个矩阵?
▷🦆
在移动过程中,如果当前元素大于目标值,为何选择向左移动而不是向上移动?
▷🦆
该算法在处理空矩阵或矩阵的某些行为空的情况下是否有特殊处理或潜在的错误?
▷