搜索二维矩阵

难度:

标签:

题目描述

给你一个满足下述两条属性的 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.length
n == matrix[i].length
1 <= m, n <= 100
-10⁴ <= matrix[i][j], target <= 10⁴

代码结果

运行时间: 40 ms, 内存: 15.2 MB

/*
 * 题目思路：
 * 1. 使用Java Stream API，通过流的方式处理二维矩阵。
 * 2. 将矩阵的每行转为流，再将每个元素转为流，然后扁平化为单个流。
 * 3. 过滤出等于目标值的元素，检查是否存在。
 */
import java.util.Arrays;
 
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        return Arrays.stream(matrix)
                     .flatMapToInt(Arrays::stream)
                     .anyMatch(value -> value == target);
    }
}

解释

方法:

该题解采用两次二分查找的思路。首先对矩阵的第一列元素进行二分查找，目的是找到目标值可能所在的行。找到后，再对该行进行二分查找，判断目标值是否存在。

时间复杂度:

O(log(m*n))

空间复杂度:

O(1)

代码细节讲解

🦆

为什么在进行第一次二分查找时，你选择比较`matrix[mid][-1]`与`target`，而不是`matrix[mid][0]`？

▷

在这种方法中，选择比较`matrix[mid][-1]`（即每行的最后一个元素）与`target`是因为我们想确认目标值可能所在的行。每行的最后一个元素是该行中最大的，如果`target`小于或等于这个元素，则目标值有可能在这行或更前面的行中。如果我们比较的是每行的第一个元素`matrix[mid][0]`，则只能告诉我们`target`是否可能在这行或更后面的行中，这不足以帮助我们准确锁定目标值的行。

🦆

在第一次二分查找中，当`matrix[mid][-1]`大于等于`target`时，为何选择将右指针`r`设置为`mid`而不是`mid + 1`？

▷

当`matrix[mid][-1]`大于等于`target`时，意味着`target`可能位于当前行或之前的行。将右指针`r`设置为`mid`，而不是`mid + 1`，是为了确保不排除当前行，因为当前行的最后一个元素大于等于`target`，所以`target`有可能正好在这一行。如果我们将`r`设置为`mid + 1`，则当前行会被排除在外，可能会错过包含`target`的行。

🦆

第一次二分查找结束后，为什么可以确定`target`只能存在于`matrix[row]`这一行中？

▷

第一次二分查找的目的是缩小目标值可能存在的行范围。结束时，`l`和`r`指针将会指向同一行，也就是变量`row`。此时，这一行是唯一一行，其最后一个元素大于等于`target`且前一行的最后一个元素（如果存在）小于`target`。因此，这一行是`target`可能存在的唯一行，接下来只需要在此行进行二分查找即可确定`target`是否真的存在于该行。

🦆

如果矩阵的每一行只包含一个元素，这种二分查找方法是否仍然有效？

▷

如果矩阵中的每一行只包含一个元素，这种二分查找方法仍然有效。在这种情况下，每一行的第一个元素也是最后一个元素，因此第一次二分查找将会找到一个最可能包含`target`的行。然后在这一行（即一个元素）进行第二次二分查找，实际上就是直接比较这一个元素与`target`。因此，整体逻辑不变，依然可以准确地判断`target`是否存在于矩阵中。

搜索二维矩阵

题目描述

代码结果

解释

代码细节讲解

相关问题

搜索二维矩阵 II