2、⼆维数组中的查找

题目描述

在⼀个⼆维数组中（每个⼀维数组的⻓度相同），每⼀⾏都按照从左到右递增的顺序排序，每⼀列都按照从上到下递增的顺序排序。请完成⼀个函数，输⼊这样的⼀个⼆维数组和⼀个整数，判断数组中是否含有该整数。

例⼦

输⼊⼀个数组：

num[3][4] = [
1 , 4 , 6 , 28 ,
2 , 7 , 32 , 30 ,
10 , 11 , 67 , 79
]

需要查找⼀个数字 32 ，则返回 true 。

解法及思路

暴⼒破解

直接暴⼒遍历，但是在最坏的情况是遍历完所有的元素才能获取结果。如果这个数组规模是 n * m ，那么时间复杂度就是 O(n × m) ，没有借助其他的空间，空间复杂度为 O(1) 。

public class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 检查输入是否为空或无效
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;

        // 暴力破解：遍历整个二维数组
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }

        // 如果遍历完所有元素都没有找到目标值，返回false
        return false;
    }
}

⽐较查找法

换⼀种思路，我们可以利用矩阵的排序特性可以从右上角或左下角开始查找，从而优化搜索效率。具体来说：

• 从右上角开始：
  • 如果当前元素等于目标值，返回 true。
  • 如果当前元素大于目标值，向左移动一列。
  • 如果当前元素小于目标值，向下移动一行。

这种算法的时间复杂度为 O(m + n)，其中 m 是行数，n 是列数。

public class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 检查输入是否为空或无效
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;

        // 从右上角开始查找
        int row = 0;
        int col = cols - 1;

        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--; // 向左移动一列
            } else {
                row++; // 向下移动一行
            }
        }

        // 如果遍历完所有可能的位置都没有找到目标值，返回false
        return false;
    }
}