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相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

赞 (0)

相关推荐

  • js有序数组的连接问题

    1.前言 昨天碰到一道关于如何解决有序数组的连接问题,这是一个很常见的问题.但是这里要考虑到代码的效率问题,因为要连接的数组都是有序的,这是一个非常重要的前提条件. 2.简单但效率不高的算法 我首先想到的是使用内置的concat方法,然后再对其进行排序,这种方法完全没有考虑到数组是有序的前提条件,代码如下: 复制代码 代码如下: function concatSort(arrA,arrB){      return arrA.concat(arrB).sort(); } 为了弄清楚sort排序到

  • C语言实现在数组A上有序合并数组B的方法

    本文实例讲述了C语言实现在数组A上有序合并数组B的方法,分享给大家供大家参考.具体分析如下: 题目:数组A和数组B均有序,数组A有足够大内存来容纳数组B,将数组B有序合并到数组A中 分析:如果由前至后合并,复杂度将会是O(N2),这样的复杂度显然不是最优解,利用两个指针指向两个数组的尾部,从后往前遍历,这样的复杂度为O(n2) 由此可以写出下面的代码: #include <iostream> #include <algorithm> #include <iterator>

  • java实现向有序数组中插入一个元素实例

    整理文档,搜刮出一个java实现向有序数组中插入一个元素,稍微整理精简一下做下分享 package cn.jbit.array; import java.util.*; public class Insert { public static void main(String[] args) { //字符排序 char[] chars = new char[9]; chars[0] = 'a'; chars[1] = 'c'; chars[2] = 'u'; chars[3] = 'b'; cha

  • 归并算法之有序数组合并算法实现

    归并算法之有序数组合并算法实现 一个简单的有序数组合并算法:写一个函数,传入 2 个有序的整数数组,返回一个有序的整数数组.实现相当简单,创建一个长度为这两个长度之和的数组,然后分别用三个指针指向这三个数组,找到这两个数组中各个元素在合并数组中的位置并插入,直到某个数组指针到达尾部.再将另一个数组剩下的所有元素,直接放入归并数组尾部.算法的简单实现,需要注意的是对参数的校验,判断数组是否有序. public class MergeOrderedArray { public static int[

  • php判断一个数组是否为有序的方法

    本文实例讲述了php判断一个数组是否为有序的方法.分享给大家供大家参考.具体分析如下: 这段代码的时间复杂度为O(n) <?php function JudegSortArray($array) { if ($array [0] > $array [1]) { $flag = 1; } else { $flag = 0; } $temp = $flag; $len = count ( $array ); for($i = 1; $i < $len; $i ++) { if ($flag

  • javascript 折半查找字符在数组中的位置(有序列表)

    复制代码 代码如下: /** * 折半查找字符在数组中的位置(有序列表) * @param array 被检索的数组 * @param x 要查找的字符 * @type int * @returns 字符在数组中的位置,没找到返回-1 */ function binarySearch(array,x){ var lowPoint=1; var higPoint=array.length; var returnValue=-1; var midPoint; var found=false; whi

  • 合并有序数组的实现（java与C语言）

    合并有序数组的实现 java版本: 实例代码 public class Merge { //合并有序数组 public static void mergeSort(int a[], int b[], int c[]) { int n = a.length, m = b.length; int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) { c[k++] = a[i++]; } else

  • 用递归查找有序二维数组的方法详解

    假设给定一个有序二维数组,每一行都是从左到右递增,每一列都是从上到下递增,如何完成一个函数,输入这样一个二维数组和一个整数,判断这个整数是否在这个二维数组中.假设一个4×4的有序二维数组:          1          2          8          9          2          4          9          12          4          7          10        13          6          8 

  • php实现有序数组打印或排序的方法【附Python、C及Go语言实现代码】

    本文实例讲述了php实现有序数组打印或排序的方法.分享给大家供大家参考,具体如下: 有序的数组打印或排序对于php来讲非常的简单了这里整理了几个不同语言的做法的实现代码,具体的我们一起来看这篇php中有序的数组打印或排序的例子吧. 最近有个面试题挺火的--把2个有序的数组打印或排序,刚看到这个题的时候也有点蒙,最优的算法肯定要用到有序的特性. 思考了一会发现也不是很难,假如数组是正序排列的,可以同时遍历2个数组,将小的值进行排序,最后会遍历完一个数组,留下一个非空数组,而且剩下的值肯定大于等于已

  • Python实现二维有序数组查找的方法

    本文实例讲述了Python实现二维有序数组查找的方法.分享给大家供大家参考,具体如下: 题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 这题目属于比较简单但又很不容易想到的,问了两个同学,大家一时都没有想出来怎么解决比较快.第一反应都是二分查找.对于每一行进行二分查找,然后查找过程可以把某些列排除掉,这是大家都能想到的基本的思路. 比较好的另一种思路是,首先选取数组右上角

  • Python识别二维码的两种方法详解

    Python识别二维码的两种方法详解

    目录 前言 pyzbar + PIL cv2 前言 最近在搜寻资料时,发现了一则10年前的新闻:二维码将成线上线下关键入口.从今天的移动互联网来看,支付收款码/健康码等等与我们息息相关,二维码确实成为了我们生活中不可或缺的一部分. 在学习Python处理二维码的过程中,我们看到的大多是“用python生成酷炫二维码”.“用Python制作动图二维码”之类的文章.而关于使用Python批量识别二维码的教程,并不多见.所以今天我会给大家分享两种批量识别二维码的Python技巧! pyzbar + P

  • Python创建二维数组实例(关于list的一个小坑)

    0.目录 1.遇到的问题 2.创建二维数组的办法 •3.1 直接创建法 •3.2 列表生成式法 •3.3 使用模块numpy创建 1.遇到的问题 今天写Python代码的时候遇到了一个大坑,差点就耽误我交作业了... 问题是这样的,我需要创建一个二维数组,如下: m = n = 3 test = [[0] * m] * n print("test =", test) 输出结果如下: test = [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 是不是看起来没有一点问

  • Python实现二维数组按照某行或列排序的方法【numpy lexsort】

    本文实例讲述了Python实现二维数组按照某行或列排序的方法.分享给大家供大家参考,具体如下: lexsort支持对数组按指定行或列的顺序排序:是间接排序,lexsort不修改原数组,返回索引. (对应lexsort 一维数组的是argsort a.argsort()这么使用就可以:argsort也不修改原数组, 返回索引) 默认按最后一行元素有小到大排序, 返回最后一行元素排序后索引所在位置. 设数组a, 返回的索引ind,ind返回的是一维数组 对于一维数组, a[ind]就是排序后的数组.

  • Python输入二维数组方法

    前不久对于Python输入二维数组有些不解,今日成功尝试,记以备忘.这里以输入1-9,3*3矩阵为例 n=int(input()) line=[[0]*n]*n for i in range(n): line[i]=input().split(' ') print(line) 使用数据转换为int即可! 以上这篇Python输入二维数组方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们. 您可能感兴趣的文章: 一些Python中的二维数组的操作方法 python中字

  • Python实现二维数组输出为图片

    对于二维数组,img_mask [[ 0 0 0 ..., 7 7 7] [ 0 0 0 ..., 7 7 7] [ 0 0 0 ..., 7 7 7] ..., [266 266 266 ..., 253 253 253] [266 266 266 ..., 253 253 253] [266 266 266 ..., 253 253 253]] 显示为图片的代码为: import matplotlib.pyplot as pyplot pyplot.imshow(im_mask) 以上这篇P

  • python 去除二维数组/二维列表中的重复行方法

    之前提到去除一维数组中的重复元素用unique()函数,如果要去除二维数组中的重复行该怎么操作呢? import numpy as np arr = np.array([[1, 2],[3, 4],[5, 6],[7, 8],[3, 4],[1, 2]]) print(np.array(list(set([tuple(t) for t in arr])))) 输出: [[1 2] [3 4] [5 6] [7 8]] 如果是二维列表,列表中每个元素还是列表 list2=list(set([tup

  • python实现二维数组的对角线遍历

    本文实例为大家分享了python实现二维数组的对角线遍历,供大家参考,具体内容如下 第一种情况:从左上角出发,右下角结束 要完成的事情,就像下图: 话不多说,直接上Python实现代码与结果展示: # 输出遍历的索引与其对应的值 A = [[1,2,3], [4,5,6], [7,8,9]] n = len(A) for i in range(n+n-1): for j in range(i+1): k = i-j if k<n and k>=0 and j<n: print("

  • Python获取二维数组的行列数的2种方法

    这篇文章主要介绍了Python获取二维数组的行列数的2种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 import numpy as np x = np.array([[1,2,5],[2,3,5],[3,4,5],[2,3,6]]) # 输出数组的行和列数 print x.shape # (4, 3) # 只输出行数 print x.shape[0] # 4 # 只输出列数 print x.shape[1] # 3 或者 In [48]

  • Python创建二维数组与初始化的实践举例

    目录 一.Python用什么表达二维数组 二.如何初始化一个二维数组 2.1 利用list自身进行构造 2.2 利用传统的list的append方法,通过迭代构造 2.3利用numpy包构建二维数组(矩阵) 三.操作二维数组 一.Python用什么表达二维数组 严格意义上说,Python中并没有数组的概念,Python中表达一组数据有多种形式,例如list,tuple,set等数据结构都可以表达一组数,并且这组数也没有C和C++中数组的的同质限制,这些数可以是任何一种数据类型. 以list为例(

随机推荐