剑指刷题2

面试题4: 二维数组中的查找

题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路：还是一样，我们考虑的是要复杂度越小越好，所以打消遍历整个数组的念头吧。我们可以通过比较选取的点和我们要找的点的大小关系，来排除候选的点（排除一整行或者是一整列），直到找到目标或者无候选点。这个遍历的起始位置只能选择矩阵的左下角或者右上角，只有这样才能排除候选点。

class Solution:
    def searchMatrix(self, matrix, target):
        # an empty matrix obviously does not contain `target` (make this check
        # because we want to cache `width` for efficiency's sake)
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False

        # cache these, as they won't change.
        height = len(matrix)
        width = len(matrix[0])

        # start our "pointer" in the bottom-left
        row = height-1
        col = 0

        while col < width and row >= 0:
            if matrix[row][col] > target:
                row -= 1
            elif matrix[row][col] < target:
                col += 1
            else: # found it
                return True
        
        return False

代码思路：还是一样，先排除一下异常的情况，行数(len(matrix))和列数(len(matrix[0]))都不能为零。然后就是按照大小关系去排除（移动）了。

形象的过程可以看：leetcode