题干

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例:

现有矩阵 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]
]

给定 target = 5,返回 true

给定 target = 20,返回 false

思路:

关键点肯定在矩阵的数据特性上:从左到右升序,从上到下升序。那么高效的搜索算法该怎么写呢?

因为之前并没有刷搜索类型的题目,而是从数据结构开始刷的,所以此时脑子里没什么思路,之前接触到的搜索也只记得起来一个 二分搜索,所以直接看答案把。

答案思路:

  • 方法一暴力查找,遍历矩阵,匹配查找的元素。【这个思路肯定是正确的,但是也肯定对不上"高效"这两个字,不过既然看了思路,那就自己实现一下吧,就当做第一步,先把功能做出来再说】

复杂度分析

时间复杂度O(mn)O(mn)。因为我们在 n * m 矩阵上操作,总施加你复杂读为矩阵的大小。

空间复杂度O(1),暴力法分配的额外空间不超过少量指针,因此内存占用是恒定的。

   /**
     * 2020-08-15 23:51:10
     * LeetCode-Array-medium-240-搜索二维矩阵
     * 给定一个二维矩阵,给定一个要搜索的值,返回该矩阵是否包含该值
     *
     * @param matrix 给定矩阵
     * @param target 查找值
     * @return 查找值是否在矩阵中存在
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        // 边界确认
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        // 1. 遍历数组比对target
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }

image-20200815235837516

这种解法真的很简单,但是完全不符合题意,还是继续看下面的解法吧。

  • 方法二二分法搜索。 由于矩阵已经是有序的,所以可以使用二分法加快我们的算法。 【其实我刚开始是想用 Arrays.binarySerarch() 来做的,但是看了下,JDK只实现了普通数组的查找,并没有提供对二维数组查找的支持,所以作罢。】

算法:首先确保矩阵不为空【边界条件的确认】,所以可以从矩阵的对角线进行迭代,从当前元素对列和行同时搜索,我们可以保持从当前(row、col) 对开始的行和列为已排序,因此总是可以二分搜索这些行和列的切片。

以如下逻辑进行:在对角线上迭代,二分搜索行和列,直到对角线迭代元素用完(返回 false)或者找到目标(返回 ture)

二维数组的二分搜索和普通的一样,但需要同时搜索二维数组的行和列。

【以上为官方答案,看完明确了核心:对同时进行二分搜索,但是让我直接实现的话,又写不出来。】

   // 首先是独立出一个二分搜索的算法,给定是横排还是竖排,起始值,然后开始搜索,这个还是需要画图更直接一些
    /**
     * @param martrix 给定矩阵
     * @param target 要查找的元素
     * @param start 起始元素
     * @param vertical 是竖直还是水平搜索
     * @return 元素是否存在
     */
    private  boolean binarySearch(int[][] martrix, int target, int start, boolean vertical) {
        int lo = start;
        // 如果是竖直的,就获取竖直数组的最后一个元素,否则获取水平数组的最后一个元素
        int hi = vertical ? martrix[0].length - 1 : martrix.length - 1;

        while (hi >= lo) {
            // 找到中间元素
            int mid = (lo + hi) / 2;
            // 针对列查找
            if (vertical) {
                // 如果中间元素比目标元素小,最低值向右移动一位
                if (martrix[start][mid] < target) {
                    lo = mid + 1;
                    // 如果中间元素比目标值大,最高值向左移动1位
                } else if (martrix[start][mid] > target) {
                    hi = mid - 1;
                } else {
                    // 这是直接相等的情况了
                    return true;
                }
            } else { // 查找的是 行
                if (martrix[mid][start] < target) {
                    lo = mid + 1;
                } else if (martrix[mid][start] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            }
        }
        return false;
    }

   /**
     * 使用二分法查找矩阵中的元素,调用上面的算法
     * @param matrix
     * @param target
     * @return
     */
    public  static boolean searchMatrixBinary(int[][] matrix, int target) {
        // 边界确认
        if (matrix == null || matrix.length == 0) {
            return false;
        }

        // 遍历数组的对角线
        int shortDim = Math.min(matrix.length, matrix[0].length); // 返回行和列更小的那个

        for (int i = 0; i < shortDim; i++) {
            // 竖排查找
            boolean verticalFound = binarySearch(matrix, target, i, true);

            // 横排查找
            boolean horizontalFound = binarySearch(matrix, target, i, false);

            if (verticalFound || horizontalFound) {
                return true;
            }
        }
        return false;
    }

image-20200816010744187

但是并没有跟我想象中一样快非常多。

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

最是人间留不住,曾是惊鸿照影来。