3.6 Search a 2D Matrix II搜索二维矩阵 II

在线题测：https://www.lintcode.com/problem/search-a-2d-matrix-ii/description

在线题解：https://www.jiuzhang.com/solution/search-a-2d-matrix-ii/

38.搜索二维矩阵 II

写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。

这个矩阵具有以下特性：

• 每行中的整数从左到右是排序的。
• 每一列的整数从上到下是排序的。
• 在每一行或每一列中没有重复的整数。

样例

例1:

输入:
[[3,4]]
target=3
输出:1
例2:

输入:
    [
      [1, 3, 5, 7],
      [2, 4, 7, 8],
      [3, 5, 9, 10]
    ]
    target = 3
输出:2

挑战

要求O(m+n) 时间复杂度和O(1) 额外空间

更新代码：

class Solution:
    """
    @param matrix: An list of lists of integers
    @param target: An integer you want to search in matrix
    @return: An integer indicates the total occurrence of target in the given matrix
    """
    def searchMatrix(self, matrix, target):
        if matrix == [] or matrix[0] == []:
            return 0

        row, column = len(matrix), len(matrix[0])
        i, j = row - 1, 0
        count = 0
        while i >= 0 and j < column:
            if matrix[i][j] == target:
                count += 1
                i -= 1
                j += 1
            elif matrix[i][j] < target:
                j += 1
            elif matrix[i][j] > target:
                i -= 1
        return count