在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
给定 target = 5，返回 true。 给定 target = 20，返回 false。
限制： 0 <= n <= 1000 0 <= m <= 1000
算法思想：
从矩阵右上角开始。target小于矩阵元素值，列-1；target大于矩阵元素值，行+1。每次迭代都排除一行或一列。
算法时间复杂度：
O( m + n ) from typing import List from ast import literal_eval class Solution: def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool: if matrix and matrix[0]: row = 0 row_high = len(matrix)-1 col = len(matrix[0]) - 1 col_low = 0 while row <= row_high and col >= col_low: temp = matrix[row][col] if target == temp: return True elif target < temp: col -= 1 else: row += 1 return False if __name__ == '__main__': solution = Solution() matrix = literal_eval(input('matrix: ').strip()) while True: target = literal_eval(input('target: ').strip()) result = solution.findNumberIn2DArray(matrix, target) if target is False: break print(result) """ 运行结果： matrix: [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]] target: 5 True target: False Process finished with exit code 0 """[题目来于Leetcode中剑指offer]
