专栏首页AI算法与图像处理《剑指offer》二维数组中的查找——巧妙解法

《剑指offer》二维数组中的查找——巧妙解法

一、题目描述

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

输入数组:

[
  [1,2,8,9],
  [2,4,9,12],
  [4,7,10,13],
  [6,8,11,15]
]

如果输入查找数值为10,则返回true,

如果输入查找数值为5,则返回false。

我们一步一步的挖掘题目的精髓,寻找一个优秀的解法

(1)根据题目的描述,很容易想到暴力解法。那太low了。

(2)再仔细观察二维数组的特点,每行每列都是递增的,那么可以使用逐行(或逐列)二分法查找的方法呀,比方法(1)优秀一些,但是好像也只是利用行或列的递增,并没有将二者结合起来。

(3)因此引出了,最终版的解法(单调性扫描法)。

接下来用图的方式清晰的讲解其原理

二、图文描述

假设输入数组:

假设输入的查找数值为 target=10:

通过将target=10 与 “每一行”的最后一个数字(9),进行比较的方式依次进行。

no pic u say a J8

好的接下来看图

因为行(i)从左到右是递增的关系,列(j)从上到下是递增关系,因此,利用这个单调性可以这种去操作:

每次都利用target与数组的右上角的数进行比较

(1)第一轮比较过程

如果 target=10,大于数组a[0][3]=9(第一行最大值),那么第一行的所有数都不满足要求。

直接查找下一行 ==> i++

(2)第二轮比较过程

target=10,与a[1][3]=12(最后一列的最小值)进行比较,此时target=10<12,那么这列的所有数必定都不满足要求。

直接查找前一列 ==> j--

(3)第三轮比较过程

target=10,与a[1][2]=9(当前行最大值)进行比较,此时target=10>9,那么这行的所有数必定都不满足要求。

直接查找下一行 ==> i++

是不是非常的清晰,而且效率极高,有效的利用了题目中提供的条件。

三、代码实现

Python版

class Solution:
    # array 二维列表
    def Find(self, target, array):
        if (len(array)==0 or len(array[0])==0):
          return False
        i=0
        j=len(array[0])-1
        while (i<len(array) and j>=0):
            if array[i][j]==target:
                return True
            elif array[i][j]>target:
                j -= 1
            else:
                i += 1
        return False

C++版

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if (array.empty() || array[0].empty()) return false;
        int i=0, j=array[0].size()-1;
        while(i<array.size() && j>=0){
            if (array[i][j]==target) return true;
            if (array[i][j]>target) j--;
            else i++;
        }
        return false;
    }
};

四、时间复杂度分析

每一步会排除一行或者一列,矩阵一共有 n 行,m 列,所以最多会进行 n+m步。所以时间复杂度是 O(n+m)。

本文分享自微信公众号 - AI算法与图像处理(AI_study),作者:AI_study

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

原始发表时间:2020-04-12

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 初学者必备的数组相关知识点

    作者是一名在读的大二学生,在我看来,是一个非常励志的小伙子,虽然他总觉得自己并不是读的名校,有点小小的不自信,但我相信这么早就意识到学习重要性的小伙子未来可期。

    AI算法与图像处理
  • 非CS科班算法岗(规控方向)面经

    先说一下背景,top2本博控制专业,一年前没有任何数据结构和算法系统知识,一年内系统的选了数据结构和算法课,同时先后经历了春招实习和秋招校招的洗礼,也完成了自己...

    AI算法与图像处理
  • You Only Watch Once:实时人体动作定位网络

    今天跟大家介绍一篇YOLO风格浓郁的论文,来自慕尼黑工业大学的学者受人类视觉的启发,提出一种快速实时的视频动作定位方法You Only Watch Once(Y...

    AI算法与图像处理
  • 【大厂面试题】笔试题明明已经AC了,为什么还是把我挂掉了?乔戈里告诉你为什么

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

    乔戈里
  • Day42:和为S的两个数字

    思路二: 1.定义两个指针,第一个指向第一个元素,第二个指向最后一个元素; 2.先拿第一个元素和最后一个元素相加,与要求的数字进行比较;   1)如果...

    stefan666
  • 30天敏捷结果(10) - 强化你的一周

       “Life is not measured by the number of breaths we take, but by the moments th...

    用户1172223
  • shell学习二数组 原

    类似与C语言,数组元素的下标由0开始编号。获取数组中的元素要利用下标,下标可以是整数或算术表达式,其值应大于或等于0。

    用户2603479
  • 递归+回溯求解数独问题

    导读:回溯是常用的算法理论之一,很多规模较大、直接分析较为复杂的问题都可以考虑用回溯求解,例如N皇后问题、骑士周游和走迷宫问题等。本质上,回溯问题是一种优化后的...

    luanhz
  • 深入理解变量对象、作用域链和闭包

    执行上下文、执行栈、作用域链、闭包,这其实是一整套相关的东西,之前转载的文章也有讲到这些。下面两篇文章会更加详细地解释这些概念。

    Chor
  • 几类关系型数据库的数据解决方案

    今天聊下几类关系型数据库的数据解决方案,算是抛砖引玉,近期也要对技术方向上做一些扩展,也算是前期的小结吧。 Oracle 目前市面上的主流版本应该还是11g...

    jeanron100

扫码关注云+社区

领取腾讯云代金券