问题描述

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。

请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

样例

输入数组:

[
  [1,2,8,9],
  [2,4,9,12],
  [4,7,10,13],
  [6,8,11,15]
]

如果输入查找数值为7,则返回true,

如果输入查找数值为5,则返回false。

解决方案

利用数组的特点,从第一行开始,我们每次让数组的每行的最后一个和目标值进行比较。具体算法如下:

  1. 行序列 i 初始化为0,列序列 j 初始化为数组的列数;
  2. 写一个while循环判断: array[i][j] 和 target 的大小关系:
  • array[i][j] < target, 说明这一行的数都比较目标值小,则意味着行序列需要增加;
  • array[i][j] > target, 说明目标值可能就在这行,我们让列序列减小;
  • array[i][j] = target, 那就说明找到了,返回True就好了
  1. 如果while循环都走完了,则只能说明这个数组中没有这个数,返回False
class Solution(object):
    def searchArray(self, array, target):
        """
        :type array: List[List[int]]
        :type target: int
        :rtype: bool
        """
        
        len_line = len(array) - 1
        if len_line <1:
            return False
        len_column = len(array[0])-1
        i = 0
        j = len_column
        while i <= len_line and j >= 0:
            if array[i][j] < target:
                i += 1
            elif array[i][j] > target:
                j -= 1
            else:
                return True
        return False