leetcode
leetcode 2551 ~ 2600
寻找目标值 - 二维数组

寻找目标值 - 二维数组

难度:

标签:

题目描述

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)

代码细节讲解

🦆
在题解中,你是如何确定从右上角开始搜索的初始位置,而不是其他角落的元素?
从右上角开始搜索的方法是基于矩阵的行和列都是递增的特性。右上角的元素具有独特的属性:它是所在行中最大的同时也是所在列中最小的。这种属性使得每一步决策(向左或向下移动)能有效地排除一行或一列。相比之下,从左上角开始,向右和向下都是递增,无法有效使用目标值与当前元素的比较来排除行或列;从左下角或右下角开始类似,都不如右上角的起始位置有效。
🦆
如果目标值等于右上角的元素,搜索过程是否会立即终止,还是会继续搜索整个矩阵?
如果目标值等于右上角的元素,搜索过程会立即终止。根据代码逻辑,检查到目标值等于当前元素时,会直接返回True,表示找到了目标值,无需进一步搜索其他部分的矩阵。
🦆
在移动过程中,如果当前元素大于目标值,为何选择向左移动而不是向上移动?
在当前元素大于目标值时选择向左移动而不是向上移动,是因为向上移动到上一行仍然会面对同样大或更大的元素,因此不能有效排除任何错误的可能性。而向左移动可以排除当前列中所有较大的元素,因为整列元素都是递增的。这样做有效缩小了搜索范围,增加了查找效率。
🦆
该算法在处理空矩阵或矩阵的某些行为空的情况下是否有特殊处理或潜在的错误?
该算法确实对空矩阵或部分空行有处理,这体现在初始化列索引时用到的条件表达式 `len(matrix) and len(matrix[0])`。这一表达式确保如果矩阵为空或任何一行为空,则列索引为0,从而使得循环条件不成立,直接返回False。因此,算法能正确处理空矩阵或含空行的情况,不会引发错误。

相关问题