Python实现杨氏矩阵高效查找算法

阿麦

发布时间：2026-10-13 | 4人浏览过

原创

本文介绍利用Python解决杨氏矩阵查找问题的具体实现。针对每行从左到右、每列从上到下递增的二维数组，通过从右上角或左下角出发，每次比较可排除一行或一列，从而高效判断整数是否存在。文章提供了完整的AC代码及错误处理逻辑，适合算法学习与实战参考。

Python杨氏矩阵查找算法实现

本文分享使用Python语言实现杨氏矩阵查找功能的具体代码示例，供读者参考学习。

问题描述：

给定一个m行n列的二维数组，其中每一行元素从左到右递增排序，每一列元素从上到下递增排序。请编写一个函数，接收该二维数组和一个目标整数，判断数组中是否包含该整数。若存在则返回1，不存在则返回0，若输入参数错误则返回“input error”。

问题分析：基于杨氏矩阵的特性，左上角元素为最小值，右下角元素为最大值。若从左上或右下角开始比较，每次仅能排除一个元素。而选择从左下角或右上角开始比较，每次比较均可排除一整行或一整列，从而显著提升查找效率。

算法逻辑与AC代码示例

以下AC代码以右上角为起始点为例进行演示：

当右上角元素大于目标数字时，说明目标不可能在当前行，故排除当前行（列索引减1）；
当右上角元素小于目标数字时，说明目标不可能在当前列，故排除当前列（行索引加1）；
若两者相等，则查找成功，返回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())

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

以上就是本文的全部内容，希望对各位的学习有所帮助，也欢迎大家继续支持本站。