[LeetCode] Search a 2D Matrix II (Python3)

leetcode

The search itself is pretty heuristic; the important question is, where to start?

It’s common to think that you should start from the origin, left-top corner. However, it is not the best idea because it’s the smallest, and you will have to go radially because the distribution is symmetrical according to the diagonal line from top-left to bottom-right.

That is to say, if you search from bottom-left, or top-right, and go diagonally, you will only search the minimum elements, which is the most efficient.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    """
    @param matrix: A list of lists of integers
    @param target: An integer you want to search in matrix
    @return: An integer indicate the total occurrence of target in the given matrix
    """
    def searchMatrix(self, matrix, target):
        # write your code here
        if matrix == []: return 0
        i = len(matrix) - 1
        j = 0
        n = len(matrix[0])
        count = 0
        while True:
            if matrix[i][j] == target:
                count += 1
                i -= 1
                j += 1
            # not equal
            elif matrix[i][j] < target:
                j += 1
            else: # bigger
                i -= 1
            if i < 0 or j >= n:
                break
        return count