原題

寫出一個(gè)高效的算法來搜索m×n矩陣中的值，返回這個(gè)值是否出現(xiàn)。
這個(gè)矩陣具有以下特性：
每行中的整數(shù)從左到右是排序的。
每一列的整數(shù)從上到下是排序的。
在每一行或每一列中沒有重復(fù)的整數(shù)。

考慮下列矩陣：

[
    [1, 3, 5, 7],
    [2, 4, 7, 8],
    [3, 5, 9, 10]
]

給出target = 3，返回 True

解題思路

• 思考時(shí)間復(fù)雜度時(shí)，可以從有多少個(gè)答案的角度考慮，像permutation時(shí)間復(fù)雜度肯定是2^{n而不會(huì)是n}2
• [Search a 2D Matrix I]是每一行的最后一個(gè)都小于下一行的第一個(gè)，所以可以把整個(gè)二維數(shù)組看成遞增的一維數(shù)組，而本題不同。
• 把起始點(diǎn)設(shè)為左下角，如本題，如果target > 3則第一列跳過，如果target < 3則最后一行跳過

完整代碼

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix:
            return 0
            
        depth = len(matrix)
        width = len(matrix[0])
        row, col = depth - 1, 0
        while row >= 0 and col < width:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                row -= 1
            else:
                col += 1
        return False