二维数组中的查找

😀前言
在解决问题时，我们经常会遇到需要在二维数组中查找特定元素的情况。然而，如果直接使用暴力搜索，即遍历整个数组寻找目标元素，可能会导致时间复杂度较高，效率不高。然而，对于给定的二维数组，如果我们能够利用其特殊的排序性质，就有可能实现更高效的查找算法。

🏠个人主页：尘觉主页

文章目录

二维数组中的查找
- 题目链接
- 题目描述
- 解题思路
- 思路分析
- 😄总结

二维数组中的查找

题目链接

牛客网

题目描述

给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。

Consider the following 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.

解题思路

要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为列数。

该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来快速地缩小查找区间，每次减少一行或者一列的元素。当前元素的查找区间为左下角的所有元素。

35a8c711-0dc0-4613-95f3-be96c6c6e104

public boolean Find(int target, int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
        return false;
    int rows = matrix.length, cols = matrix[0].length;
    int r = 0, c = cols - 1; // 从右上角开始
    while (r <= rows - 1 && c >= 0) {
        if (target == matrix[r][c])
            return true;
        else if (target > matrix[r][c])
            r++;
        else
            c--;
    }
    return false;
}

思路分析

首先，我们观察到这样一个规律：对于二维数组中的任意一个数，它位于当前行的最右边、当前列的最上方。根据这个规律，我们可以将整个查找过程看作是从矩阵的右上角开始逐步移动，根据目标值与当前元素的大小关系，决定是向左移动一列，还是向下移动一行，直到找到目标值或者遍历完整个数组。

具体算法步骤如下：

首先，我们对输入进行异常情况的处理。如果输入的二维数组为空或者行列数为0，则直接返回false，表示不存在目标值。

然后，我们初始化两个指针r和c，分别指向矩阵的右上角元素。初始时，r指向第一行，c指向最后一列。

进入循环，循环条件为r小于行数且c大于等于0。这是因为如果r越界，则说明已经遍历完所有行；如果c越界，则说明已经遍历完所有列。

在循环中，我们首先检查当前指向的元素是否等于目标值。如果等于，则直接返回true，表示目标值存在于二维数组中。

如果当前元素不等于目标值，我们根据当前元素与目标值的大小关系决定移动指针。如果目标值大于当前元素，则说明目标值应该在当前元素的下方，因此将指针r向下移动一行；如果目标值小于当前元素，则说明目标值应该在当前元素的左边，因此将指针c向左移动一列。

循环结束后，如果仍然没有找到目标值，则返回false，表示目标值不存在于二维数组中。

这样，通过每次将查找区间缩小一行或者一列的方式，我们可以在时间复杂度为O(M + N)的情况下，高效地判断目标值是否存在于二维数组中。

😄总结

通过本文介绍的方法，我们可以在给定的二维数组中高效地查找目标元素。利用该二维数组的特殊排序性质，我们可以从右上角开始查找，根据目标元素与当前元素的大小关系，逐步缩小查找范围，直至找到目标元素或者确定其不存在于数组中。这种算法的时间复杂度为 O(M + N)，空间复杂度为 O(1)，具有很高的效率和实用性。因此，在解决类似问题时，我们可以考虑利用数组的特殊性质，设计出更加高效的算法，从而提升程序的性能。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持