本文共 1671 字，大约阅读时间需要 5 分钟。
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
主要思路：首先选取右上角的数字，如果该数字大于target，则该列全大于target，删除该列；如果该数字小于小于target，则该列全小于target，删除该行。 从右上角元素开始，当没到左下角元素前，不断判断右上角元素和target的关系，可以不断缩小查找范围。
1 # -*- coding:utf-8 -*- 2 class Solution: 3 # array 二维列表 4 def insert2dArray(self, seq, row, col): 5 # 没有使用numpy的array 6 # array = [[0] * col] * row 这种方式是浅拷贝，不好用 7 array = [[0 for i in range(col)] for i in range(row)] 8 for i in range(row): 9 for j in range(col):10 array[i][j] = seq[i * row + j]11 return array12 13 def Find(self, target, array):14 # 主要思路：首先选取右上角的数字，如果该数字大于target，则该列全大于target，删除该列；15 # 如果该数字小于小于target，则该列全小于target，删除该行。16 found = False17 row = len(array)18 if row:19 col = len(array[0])20 else:21 col = 022 23 if row > 0 and col > 0:24 # find index of top right-hand corner25 i = 026 j = col - 127 # if never meets lower-left corner28 while i < row and j >= 0:29 if array[i][j] == target:30 found = True31 # forget break32 break33 elif array[i][j] > target:34 j -= 135 elif array[i][j] < target:36 i += 137 return found38 39 if __name__ == '__main__':40 answer = Solution()41 seq = [1, 2, 8, 9, 2, 4, 9, 12, 4, 7, 10, 13, 6, 8, 11, 15]42 matrix = answer.insert2dArray(seq, 4, 4)43 print(matrix)44 print(answer.Find(7, matrix))
转载地址：http://gytgn.baihongyu.com/