LeetCode刷题-二维数组中的查找

2021-07-17 本文已影响0人小鲨鱼FF

前言说明

算法学习，日常刷题记录。

题目连接

二维数组中的查找

题目内容

在一个n * m的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵matrix如下：

矩阵

给定target = 5，返回true。

给定target = 20，返回false。

限制:

0 <= n <= 1000

0 <= m <= 1000

分析过程

方法1

直接用暴力算法，两层遍历查找，代码如下：

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 暴力算法，直接两层遍历查找
        for (int[] nums : matrix) {
            for (int num : nums) {
                if (target == num) {
                    // 若找到target，返回true
                    return true;
                }
            }
        }

        // 若两层遍历完也找不到target，返回false
        return false;
    }
}

提交代码，运行结果如下：

方法1运行结果

执行用时0ms，时间击败100.00%的用户，内存消耗4MB，空间击败78.44%的用户。

方法2

方法1为暴力破解，肯定是不可取的，没有使用到题目的条件：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

所以方法2采用线性查找法，利用二维数组matrix行递增和列递增的特点，不断缩小范围查找。

设置行标row初始为0，列标col初始为列长度减1，查找时若等于目标值target，返回true，结束。

若小于目标值target，行标row加1，直到找到目标值target为止，否则直到行标row等于行长度减1结束。

若大于目标值target，列标col减1，直到找到目标值target为止，否则直到行标row等于0结束。

若结束后还没有找到目标值target，返回false，结束。

例如：上面的例子查找5，行标row初始为0，列标col初始为4。

matrix[0][4] = 15，15 > 5，大于目标值target，列标col减1等于3。

matrix[0][3] = 11，11 > 5，大于目标值target，列标col减1等于2。

matrix[0][2] = 7，7 > 5，大于目标值target，列标col减1等于1。

matrix[0][1] = 4，4 < 5，小于目标值target，行标row加1等于1。

matrix[1][1] = 5，5 = 5，等于目标值target，找到目标值，返回true，结束。

代码如下：

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 线性查找法，利用行递增和列递增的特点，不断缩小范围

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            // 先把二维数组为空的情况排除掉
            return false;
        }

        // 定义行标，初始值为0
        int row = 0;
        // 定义列标，初始值为二维数组matrix的列长度减1
        int col = matrix[0].length - 1;

        // 循环，行标扩大直到二维数组matrix的行长度减1，列标缩小直到0
        while (row < matrix.length && col >= 0) {
            // 获取当前行标和列标下的二维数组matrix的元素
            int num = matrix[row][col];
            if (target == num) {
                // 若目标值target等于当前元素，那么二维数组matrix中含有目标值target，返回true
                return true;
            } else if (target > num) {
                // 若目标值target大于当前元素，行标加1
                ++row;
            } else {
                // 若目标值target小于当前元素，列标减1
                --col;
            }
        }

        // 若能循环结束，那么在二维数组matrix中没有找到目标值target，返回false
        return false;
    }
}

提交代码，运行结果如下：

方法2运行结果

执行用时0ms，时间击败100.00%的用户，内存消耗44.2MB，空间击败32.00%的用户。

总结解题

运行结果分析

运行时间：方法2的线性查找法不比方法1的暴力破解法快多少，都是击败100%。

运行空间：方法2的线性查找法比方法1的暴力破解法还要多一点。

原因：方法2的线性查找法的运行空间的确是会比方法1的暴力破解法多一点，但是运行时间相差不大可能是题目执行的用例不够大造成的。

方法1复杂度

时间复杂度：O(nm)，n为二维数组中的行长度，m为二维数组中的列长度。

因为是两层for循环嵌套遍历，第一层遍历是n次，第二层遍历是m次，所以用乘法，一共等于n * m次。

空间复杂度：O(1)。

方法2复杂度

时间复杂度：O(n + m)，n为二维数组中的行长度，m为二维数组中的列长度。

因为行标row最多加n次，列标col最多减m次，所以用加法，一共等于n + m次。