题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
思路
首先排除特殊情况。
然后从右上角开始比较,元素值 < target,则需向下移动;元素值 > target,则需向左移动。移动后的位置则可以看作子矩阵的右上角。
选择右上角的点是因为它可以较好地划分区域:向下增大,向左减小,而如果使用左上角的话,向下向右均为增大。
# -*- coding:utf-8 -*- class Solution: # array 二维列表 def Find(self, target, array): # write code here if array == [[]]: return False h = len(array) w = len(array[0]) if target < array[0][0] or target > array[h-1][w-1]: return False i = 0 j = w-1 while i < h and j >-1: if array[i][j] == target: return True elif array[i][j] < target: i += 1 elif array[i][j] > target: j -= 1 return False