专栏首页健程之道力扣74——搜索二维矩阵

力扣74——搜索二维矩阵

原题

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

示例 2:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
输出: false

原题url:https://leetcode-cn.com/problems/search-a-2d-matrix/

解题

二分查找

既然是已经排好序的,那么我第一想到的就是二分查找了。每次进行对半查找,时间复杂度O(log(mn)),应该还是很高效。

我准备将查找分成两部分,第一是二分查找找到 target 在哪一行,然后从那一行再利用二分查找找到 target 在这一行的哪个位置。

让我们来看看代码:

class Solution {

    // 总行数
    int row;
    // 总列数
    int col;

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        row = matrix.length;
        col = matrix[0].length;
        // 利用二分法查询
        return binarySearchMatrix(matrix, 0, matrix.length - 1, target);
    }

        /**
          * 查找这是矩阵的哪一行
          */
    public boolean binarySearchMatrix(int[][] matrix, int left, int right, int target) {
        if (left > right) {
            return false;
        }
        if (left == right) {
            int[] array = matrix[left];
            if (target < array[0] || target > array[col - 1]) {
                return false;
            }

                        // 从数据中心查找
            return binarySearchArray(array, 0, col - 1, target);
        }

        int middle = (left + right) / 2;
        int[] middleArray = matrix[middle];
        if (middleArray[0] > target) {
            return binarySearchMatrix(matrix, left, middle - 1, target);
        } else if (middleArray[col - 1] < target) {
            return binarySearchMatrix(matrix, middle + 1, right, target);
        } else {
            return binarySearchArray(middleArray, 0, col - 1, target);
        }
    }

        /**
          * 查找这是数组中的哪个位置
          */
    public boolean binarySearchArray(int[] array, int left, int right, int target) {
        if (left > right) {
            return false;
        }
        if (left == right) {
            return array[left] == target;
        }

        int middle = (left + right) / 2;
        if (array[middle] > target) {
            return binarySearchArray(array, left, middle - 1, target);
        } else if (array[middle] == target) {
            return true;
        } else {
            return binarySearchArray(array, middle + 1, right, target);
        }
    }
}

提交OK,其执行用时:1 ms,内存消耗:38.3 MB

优化

虽然解题成功,且效果不错,但总感觉这样写的太过。因为我将二维数组的查找分为两种情况,如果以后变成三维、四维数组,岂不是代码更长?其实这种查找都是利用的同一种思想——二分查找,那我们是否可以将其进行合并呢?

可以的,我们可以将二维数组拉长。拉成1层后,就可以直接用一维数组中的二分查找了。

让我们看看代码:

class Solution {

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int col = matrix[0].length;
        // 将二维数组拉成一维数组,利用二分法解决
        int left = 0;
        int right = matrix.length * col - 1;
        while (left <= right) {
            // 计算中间数的下标和值
            int middleIndex = (left + right) / 2;
            int middleVal = matrix[middleIndex / col][middleIndex % col];
            if (middleVal == target) {
                return true;
            }

            if (middleVal < target) {
                left = middleIndex + 1;
            } else {
                right = middleIndex - 1;
            }
        }

        return false;
    }
}

提交OK,其执行用时:0 ms,内存消耗:40.9 MB

大家知道这多余的内存消耗在哪儿呢?按道理说,跟前面的方法相比,这里不涉及递归,理论上其调用栈更少,内存消耗应该更少才对。如果大家知道的话,可以在下方评论,我将感激不尽。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题应该主要就是涉及到二分查找,然后加一些优化,应该就没有问题了。

有兴趣的话可以访问我的博客或者关注我的公众号,说不定会有意外的惊喜。

https://death00.github.io/

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java面试-动态规划与组合数

    最近在刷力扣上的题目,刷到了65不同路径,当初上大学的时候,曾在hihocoder上刷到过这道题目,但是现在已经几乎全忘光了,大概的知识点是动态规划,如今就让我...

    健程之道
  • 力扣240——搜索二维矩阵

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

    健程之道
  • 力扣221——最大正方形

    在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

    健程之道
  • 搜索二维矩阵Ⅱ

    一份执着✘
  • 直接插入排序 希尔排序

    【1 2 3 4  7 8 9】 6 插入3, 3和 9 交换,3和8交换, 3和7交换, 3和4交换

    用户2965768
  • Nth Digit

    Tyan
  • 【leetcode】3Sum Closest

    Given an array S of n integers, find three integers in S such that the sum is cl...

    阳光岛主
  • hdu------(1525)Euclid's Game(博弈决策树)

    Euclid's Game Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

    Gxjun
  • LintCode 子树题目分析代码

    有两个不同大小的二进制树: T1有上百万的节点; T2有好几百的节点。请设计一种算法,判定 T2是否为 T1的子树。

    desperate633
  • java原生实现屏幕设备遍历和屏幕采集(捕获)等功能

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    eguid

扫码关注云+社区

领取腾讯云代金券