Search 2d Matrix II

Question

Write an efficient algorithm that searches for a value in an m x n matrix, return the occurrence of it.

This matrix has the following properties:

* Integers in each row are sorted from left to right.

* Integers in each column are sorted from up to bottom.

* No duplicate integers in each row or column.

Example Consider the following matrix:

[

    [1, 3, 5, 7],

    [2, 4, 7, 8],

    [3, 5, 9, 10]

]

Given target = 3, return 2.

Challenge O(m+n) time and O(1) extra space

Thoughts

leetcode

这一题与I不同， 不能用2D转换1D的方法 才去与Diagonal Binary Search类似的方法，从右上或者左下开始

Analysis

Solution

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):
        # write your code here
        if not matrix:
            return 0
        m = len(matrix)
        n = len(matrix[0])
        row = 0
        col = n - 1
        count = 0
        while row < m and col >= 0:
            if matrix[row][col] == target:
                count += 1
                col -= 1
            elif matrix[row][col] < target:
                row += 1
            else:
                col -= 1
        return count