python实现杨氏矩阵查找

本文实例为大家分享了python实现杨氏矩阵查找的具体代码，供大家参考，具体内容如下

问题描述：

在一个m行n列二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。有则返回1，无则返回0，输入错误返回input error

问题分析：根据杨氏矩阵的规律可知，左上角是最小元素，右下角是最大元素，进行比较一次只能排除一个。而利用左下角或者右上角对比，一次可以排除一行或一列。

AC代码以右上角为例：

  • 当右上角大于要查找的数字时，排除一行；
  • 当右上角大于要查找的数字时，排除一列；
  • 相等则返回1
  • 全部查找失败则返回0

代码如下：

# coding=utf-8
import sys

def solve():
  try:
    # 获取行(n)和列(m)
    a = sys.stdin.readline().split()
    n, m = int(a[0]), int(a[1])
    arr = []
    for i in range(n):
      # 列表模拟二维数组
      p = list(map(int, sys.stdin.readline().split()))
      arr.append(p)
    # 获取要查找的数
    s = int(sys.stdin.readline().strip())
    i = 0
    j = m - 1
    while i<n and j>=0:
      if arr[i][j] == s:
        # 相等返回1查找成功
        return 1
      elif arr[i][j] < s:
        # 小于要查找的元素，行加1
        i += 1
      else:
        # 大于要查找的元素，列加1
        j -= 1
    return 0
  except Exception:
    return "input error"

if __name__ == "__main__":
  print(solve())

如有疑问，欢迎交流和指正。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Python使用min、max函数查找二维数据矩阵中最小、最大值的方法

    本文实例讲述了Python使用min.max函数查找二维数据矩阵中最小.最大值的方法.分享给大家供大家参考,具体如下: 简单使用min.max函数来得到二维数据矩阵中的最大最小值,很简单,这是因为工作需要用到一个东西所以先简单来写了一下: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找出来随机生成矩阵中的最大.最小值 ''' import time import random def random_matrix_ge

  • python实现杨氏矩阵查找

    本文实例为大家分享了python实现杨氏矩阵查找的具体代码,供大家参考,具体内容如下 问题描述: 在一个m行n列二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数.有则返回1,无则返回0,输入错误返回input error 问题分析:根据杨氏矩阵的规律可知,左上角是最小元素,右下角是最大元素,进行比较一次只能排除一个.而利用左下角或者右上角对比,一次可以排除一行或一列. AC代码以右上角为

  • 杨氏矩阵查找的JS代码

    复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="

  • C语言杨氏矩阵查找算法实例讲解

    目录 一.杨氏矩阵介绍 二.查找算法 1.查找思路 2.步骤 3.代码 三.杨氏矩阵例题 代码 特别注意 四.总结 本文以C语言实现,介绍杨氏矩阵中通用的查找算法. 一.杨氏矩阵介绍 杨氏矩阵种,每一行的数都从左到右递增,每一列的数都从上到下递增.如下图是一个简单的杨氏矩阵: 有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在. 要求:时间复杂度小于O(N) 二.查找算法 1.查找思路 杨氏矩阵是很有特点的,它有规律递增的特点决定了针对

  • C语言编程题杨氏矩阵算法快速上手示例详解

    目录 题目概要 一.解题思路 二.具体代码 题目概要 有一个数字矩阵,矩阵的每行从左到右都是递增的,矩阵从上到下都是递增的,请编写程序在这样的矩阵中查找某个数字是否存在? 一.解题思路 对于查找一个数组中元素是否存在,很多同学第一想法就是从头到尾遍历一遍.这样的想法优点是代码简单且无脑容易上手,但是这样的缺点也很明显,比如是m *n的数组,你从头到尾遍历,最坏情况要找m *n次.题目给的相关条件比如从左向右递增,从上向下递增你也完全没有使用,这样的暴力求解显然不是我们想看到的 我们来介绍一种方法

  • C语言杨氏矩阵实例教你编写

    目录 一.杨氏矩阵是什么 二.编写步骤 三.程序的改进 四.总结 一.杨氏矩阵是什么 一个数字矩阵,矩阵的每一行从左到右一次递增,矩阵从上到下递增,在这样的矩阵中查找一个数字是否存在.时间复杂度小于O(N). 二.编写步骤 1.首先给出一个三乘三的矩阵,我们想找到数字7是否在这个数组之中,如图所示. 2. 我们给出的方法是一种从右上角开始,另一种是从左下角开始.比如从右上角开始,编写一个函数. 3. 函数的编写.从右上角开始,将右上角数字与数字7比较,如果数字7大于右上角的数字(3)(因为第一行

  • 在python中使用正则表达式查找可嵌套字符串组

    在网上看到一个小需求,需要用正则表达式来处理.原需求如下: 找出文本中包含"因为--所以"的句子,并以两个词为中心对齐输出前后3个字,中间全输出,如果"因为"和"所以"中间还存在"因为""所以",也要找出来,另算一行,输出格式为: 行号 前面3个字 *因为* 全部 &所以& 后面3个字(标点符号算一个字) 2 还不是 *因为* 这里好, &所以& 没有人 实现方法如下: #e

  • Python实现的矩阵类实例

    本文实例讲述了Python实现的矩阵类.分享给大家供大家参考,具体如下: 科学计算离不开矩阵的运算.当然,python已经有非常好的现成的库:numpy(numpy的简单安装与使用可参考http://www.jb51.net/article/66236.htm). 我写这个矩阵类,并不是打算重新造一个轮子,只是作为一个练习,记录在此. 注:这个类的函数还没全部实现,慢慢在完善吧. 全部代码: import copy class Matrix: '''矩阵类''' def __init__(sel

  • Python实现螺旋矩阵的填充算法示例

    Python实现螺旋矩阵的填充算法示例

    本文实例讲述了Python实现螺旋矩阵的填充算法.分享给大家供大家参考,具体如下: afanty的分析: 关于矩阵(二维数组)填充问题自己动手推推,分析下两个下表的移动规律就很容易咯. 对于螺旋矩阵,不管它是什么鬼,反正就是依次向右.向下.向右.向上移动. 向右移动:横坐标不变,纵坐标加1 向下移动:纵坐标不变,横坐标加1 向右移动:横坐标不变,纵坐标减1 向上移动:纵坐标不变,横坐标减1 代码实现: #coding=utf-8 import numpy ''''' Author: afanty

  • python+pillow绘制矩阵盖尔圆简单实例

    python+pillow绘制矩阵盖尔圆简单实例

    本文主要研究的是使用Python+pillow绘制矩阵盖尔圆的一个实例,具体如下. 盖尔圆是矩阵特征值估计时常用的方法之一,其定义为: 与盖尔圆有关的两个定理为: 定理1:矩阵A的所有特征值均落在它的所有盖尔圆的并集之中. 定理2:将矩阵A的全体盖尔圆的并集按连通部分分成若干个子集,(一个子集由完全连通的盖尔圆组成,不同子集没有相连通的部分),对每个子集,若它恰好由K个盖尔圆组成,则该子集中恰好包含A的K个特征值. 与盖尔圆定理有关的几个推论为: 推论1:孤立盖尔圆中恰好包含一个特征值. 推论2

  • python中返回矩阵的行列方法

    实例如下所示: # TODO 返回矩阵的行数和列数 def shape(M): return len(M),len(M[0]) 以上这篇python中返回矩阵的行列方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们. 您可能感兴趣的文章: Python numpy 提取矩阵的某一行或某一列的实例 Python矩阵常见运算操作实例总结 Python表示矩阵的方法分析 Python获取二维矩阵每列最大值的方法 Python实现矩阵转置的方法分析 matlab中实现矩阵删

随机推荐