题目描述

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

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

样例

输入数组：

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

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

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

算法

(扫描法) $O(m+n)$

主要就是发现这个二维数组的规律：每行中最右侧数最大，每列中最下侧数最大。

从最右上方开始进行扫描，
若当前值array[i][j]正好等于target，返回True；
否则若当前值array[i][j]小于target，则说明当前位置正左侧的数都小于target，行号i加1；
否则若当前值array[i][j]大于target，则说明当前位置正下侧的数都大于target，列号j减1。
直至遍历到最左下方仍没有找到与target相同的值，返回False。

时间复杂度分析：最差的情况是二维数组（m*n）中没有要找的值，走了m+n步，时间复杂度$O(m+n)$。

C 代码

bool searchArray(int** array, int arrayRowSize, int arrayColSize, int target) {
    int i = 0;
    int j = arrayColSize - 1;
    while(i < arrayRowSize && j >= 0)
    {
        if(array[i][j] == target)
            return true;
        else if(array[i][j] < target)
            i++;
        else
            j--;
    }
    return false;
}

Python3 代码

class Solution(object):
    def searchArray(self, array, target):
        """
        :type array: List[List[int]]
        :type target: int
        :rtype: bool
        """
        # 如果数组为空
        if not array or not array[0]: return False
        # 获取二维数组的行数和列数
        rowLen, colLen = len(array), len(array[0])
        # 0赋给i，colLen-1赋给j
        i, j = 0, colLen - 1
        while i < rowLen and j >= 0:
            if array[i][j] == target:
                return True
            elif array[i][j] < target:
                i += 1
            else:
                j -= 1
        return False