专栏首页机器视觉CV数据结构与算法-二维数组中的查找

数据结构与算法-二维数组中的查找

题目:二维数组中的查找

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

例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字 7,则返回 true;如果查找数字 5,由于数组不含有该数字,则返回 false。

解决思路

  • 用具体的问题入手

本题以 7 为查找对象,其步骤如下: 先取右上角的数字 9,由于 9 大于要查找的 7 ,故 7 肯定不在此列,删除此列,如 (a) 所示;再取新的数字 8 ,同理 8 大于 7,不在此列,删去,此时只剩下两列,如 (b) 所示。

在剩余的两列中,右上角的 2 比 7 小,故 7 应该在 2 的下方,删除此行,如 (c) 所示;再取新的右上角的数 4,同理,7 只可能在 4 的下方,故删除此行。如 (d) 所示; 在剩余的两行两列中,再取右上角的数 7 ,此时和查找的数相同,结束,如不相同,则继续。

可以选取右上角或者左下角作为初始值,但是不能选择左上角和右下角,因为我们没办法是拿出某一行或者某一列,这样就不能缩小范围

代码实现

测试用例:

  • 要查找的数在数组中
  • 要查找的数字不在数组中(大于数组中所有的值,小于数组中所有的值,在某两个数字之间)
  • 空数组
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    # target 要查找的数
    def Find(self, target, array):
        found = False  # 标志位
        rows = len(array) 
        cols = len(array[0])
        if ((rows > 0) and (cols > 0)): # 边界检测
            row = 0
            col = cols - 1  # 从最后一列开始检查
            while((row < rows) and (col >= 0)):
                if array[row][col] == target: # 右上角的值与目标值相等就返回
                    found = True
                    break
                elif array[row][col] > target: # 右上角的值比目标值大,去掉最后一列
                    col -= 1
                else: # 当右上角的值比目标值小,就去掉这一行
                    row += 1 
        return found



def test1(f): # 查找的数在数组中
  target = 7
  arr = [[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
  assert f.Find(target, arr) == True


def test2(f):  # 空数组
  target = 7
  arr = [[]]
  assert f.Find(target, arr) == False


def test3(f):  # 查找的数不在数组中
  target = 5
  arr = [[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
  assert f.Find(target, arr) == False


def Test():
  f = Solution()
  test1(f)
  test2(f)
  test3(f)


Test()  

参考

  • https://github.com/zhedahht/CodingInterviewChinese2
  • https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

本文分享自微信公众号 - 机器视觉CV(AIandCV),作者:Leong

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【工具】图像处理调试工具(附工具下载!)

    在图像处理时,我们可能需要实时进行调试,有时候需要知道图像每个像素的具体值来帮助我们验证算法的准确性和理解算法思路。 在不同情况下,我们需要使用 Pytho...

    机器视觉CV
  • OpenCV 可视化工具

    OpenCV 传统的调试方式是 cv2.imshow() cv2.waitKey() ,即显示一张图片,然后查看之后再销毁它, 这个操作实在是太不方便了,如果调...

    机器视觉CV
  • 从原始图片数据开始构建卷积神经网络(Pytorch)

    入门机器学习的时候,我们往往使用的是框架自带的数据集来进行学习的,这样其实跳过了机器学习最重要的步骤,数据预处理,本文通过从原始数据(图片格式)到卷积神经网络的...

    机器视觉CV
  • 分治思想 : 并归排序与其时间复杂度

    这种把大问题分解成小问题来解决(治理) [ Divide And Conquer 我觉得Conquer应该翻译成解决比较好 ] 的方法被称为 ‘ 分治 ’

    执生
  • 插值查找-Java版

    1.对于数据量较大,关键字分布均匀的查找来说,插值查找要比二分查找快。 2.关键字分布不均匀的情况下,插值查找不一定比二分查找快甚至可能还慢。

    shengjk1
  • Nginx反向代理配置去除前缀

    使用nginx做反向代理的时候,可以简单的直接把请求原封不动的转发给下一个服务。设置proxy_pass请求只会替换域名,如果要根据不同的url后缀来访问不同的...

    烂猪皮
  • 聊聊「插入排序」的正确姿势

    面试官最爱考察的是一个被试者对知识掌握的灵活程度和熟练程度,当一道题目可以同时考察到被试者多个知识点的掌握程度和思考能力时,面试官最爱这样的题目,而且对于插入排...

    五分钟学算法
  • Java|实现冒泡排序

    冒泡排序是一种简单的常见的排序算法,算法重复的走访排序的数组,通过不断的两两比较,最终把最大数浮于上方,好比是可乐的气泡冒泡的过程,所以生动的称之为“冒泡排序”...

    算法与编程之美
  • 【面试】最容易被问到的N种排序算法!

    通俗地讲就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai...

    程序员小明
  • numpy模块(对矩阵的处理,ndarray对象)

    https://docs.scipy.org/doc/numpy/reference/?v=20190307135750

    小小咸鱼YwY

扫码关注云+社区

领取腾讯云代金券