Python实现二维有序数组查找的方法
作者:阿涵-_- 发布时间:2021-04-15 21:31:38
标签:Python,二维有序数组,查找
本文实例讲述了Python实现二维有序数组查找的方法。分享给大家供大家参考,具体如下:
题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
这题目属于比较简单但又很不容易想到的,问了两个同学,大家一时都没有想出来怎么解决比较快。第一反应都是二分查找。对于每一行进行二分查找,然后查找过程可以把某些列排除掉,这是大家都能想到的基本的思路。
比较好的另一种思路是,首先选取数组右上角的数字,如果该数字等于要查找的数字,则查找结束;如果该数字大于要查找的数字,剔除这个数字所在的列,如果该数字小于要查找的数字,剔除这个数字所在的行。这样每一步都可以剔除一行或一列,查找的速度比较快。
python实现的代码:
# -*- coding:utf-8 -*-
'''
题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
'''
def search(array, num):
# 参数合法性判断忽略
i = 0
j = len(array[0]) - 1
max_i = len(array) - 1
while i <= max_i and j >= 0:
if array[i][j] == num:
return True
elif array[i][j] > num:
j = j - 1
else:
i = i + 1
return False
if __name__ == '__main__':
a = [[1, 2, 8, 9],
[2, 4, 9, 12],
[4, 7, 10, 13],
[6, 8, 11, 15],
]
print search(a, 14)
print search(a, 7)
print search(a, 0)
希望本文所述对大家Python程序设计有所帮助。


猜你喜欢
- 代码如下: function astro(birth) astro="" if birth=""
- 记录使用pytorch构建网络模型过程遇到的点1. 网络模型构建中的问题1.1 输入变量是Tensor张量各个模块和网络模型的输入,一定要是
- 在昨天关于substring的blog中有如下一段代码:也许你已经发现,在Python 3中其实有办法只用一行完成函数:>>&g
- 有些时候我们发现一些模块没有提供pip install 命令和安装教程 , 只提供了一个setup.py文件 , 这个时候如何安装呢?步骤打
- 前言本文主要给大家介绍了关于python子类调用父类函数的相关内容,Python中子类中的__init__()函数会覆盖父类的函数,一些情况
- 本文实例讲述了PHP共享内存使用与信号控制。分享给大家供大家参考,具体如下:共享内存共享内存的使用主要是为了能够在同一台机器不同的进程中共享
- 目录range函数的使用第一种创建方式第二种创建方式第三种创建方式判断指定的数有没有在当前序列中循环结构总结range函数的使用作为循环遍历
- 需要用到的库有selenium,还需要安装Chrome浏览器驱动,具体如何安装我就不详述了在这里我模拟了csdn的登录过程**1**.首先打
- Python docx库代码演示安装需要lxml pip install python-docx主业务代码from openpyxl imp
- Python-pip安装失败问题一、问题描述root@ubuntu:/home/chao# apt-get install python-p
- request.jsp页面中有rocarsId,和ccrn两个text。 对应在数据库中表格 rocars表的msg_id,ccrn两个字段
- 一、色彩空间的转换代码如下:#色彩空间转换import cv2 as cvdef color_space_demo(img):
- IFRAME 元素 | iframe 对象创建内嵌浮动框架。成员表下面的表格列出了 iframe 对象引出的成员。请单击左侧的标签来选择你想
- 如何做一个文本书写器?我们有下面的的函数,可做“文本书写器”:<%function WriteToFile(FileName
- 本文实例为大家分享了python3通过qq邮箱发送邮件以及附件的具体代码,供大家参考,具体内容如下开启qq邮箱的smtp服务代码:impor
- 本文实例讲述了php与javascript正则匹配中文的方法。分享给大家供大家参考,具体如下:php中正则匹配utf-8中文: (重点是:[
- [Q]怎么样查询特殊字符,如通配符%与_ [Q]如何插入单引号到数据库表中 [Q]怎样设置事务一致性 [Q]怎么样利用光标更新数据 [Q]怎
- 如何实现优惠打折? 代码及说明见下:<%@ LANG
- 转用一门新语言通常是一项大决策,尤其是当你的团队成员中只有一个使用过它时。今年 Stream 团队的主要编程语言从 Python 转向了 G
- vue3.0 beta 版本已经发布有一阵子了,是时候上手体验一波了~注意,本文所有演示都是基于 vue3.0 beta 版本,不保证后续正