题解 | #二维数组中的查找#
二维数组中的查找
http://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e
'''
Q: 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,
每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数
,判断数组中是否含有该整数。
A1: 遍历整个二维数组, O(n^2)
A2: 从右上或者左下开始查找。从右上开始查找:如果数组中的数比这个整数大,向左移动一位,
如果数组中的数比这个数小,向下移动一位, O(n)。
'''
class Solution: def Find(self, target, array): if array == []: return False row = len(array) col = len(array[0]) i, j = 0, col - 1 while j >= 0 and i < row: if target > array[i][j]: i += 1 elif target < array[i][j]: j -= 1 else: return True return False target, array = 3, [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]] s = Solution() print(s.Find(target, array))