Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an mxn matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.

• Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target =5, returntrue.

Given target =20, returnfalse.

题目大意：

编写一个高效的算法，从一个m × n矩阵中寻找一个值。矩阵具有如下性质：

每一行的整数从左向右递增 每一列的整数从上往下递增

解题思路:

可以发现对于每个边界点而言，总有一种大小关系是无法排除区域的，而搜索时我们希望通过一次和target的比较就能减小搜索区域。首先分析如果从左上角开始搜索，由于元素升序为自左向右和自上而下，因此如果target大于当前搜索元素时还有两个方向需要搜索，不太合适。如果从右上角开始搜索，由于左边的元素一定不大于当前元素，而下面的元素一定不小于当前元素，因此每次比较时均可排除一列或者一行元素（大于当前元素则排除当前行，小于当前元素则排除当前列，由矩阵特点可知），可达到题目要求的复杂度。

For example, we start searching the matrix from top right corner, initialize the current position to top right corner, if the target is greater than the value in current position, then the target can not be in entire row of current position because the row is sorted, if the target is less than the value in current position, then the target can not in the entire column because the column is sorted too. We can rule out one row or one column each time, so the time complexity is O(m+n).

源码分析

1. 首先对输入做异常处理，不仅要考虑到matrix为空串，还要考虑到matrix[0]也为空串。

2. 注意循环终止条件。

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if matrix == [] or matrix[0] == [[]]:
            return False
        row = len(matrix)
        col = len(matrix[0])
        # 从左下角开始
        i = row - 1
        j = 0
        while i >= 0 and j <= col - 1:
            if target == matrix[i][j]:
                return True
            elif target < matrix[i][j]:
                i -= 1
            else:
                j += 1
        return False

Lintcode 另一种变形：出现次数

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

http://www.jiuzhang.com/video/search-a-2d-matrix-ii/?session_id=7

通过o(1)比较，可以删除o(n)一列或一行

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 matrix==[] or matrix == [[]]:
            return 0
        row = len(matrix)
        column = len(matrix[0])
        x = row-1
        y = 0
        result=0
        while x>=0 and y<=column-1:
            if matrix[x][y] > target:
                x-=1
            elif matrix[x][y] < target:
                y+=1
            else:
                result += 1
                y+=1
                x-=1
        return result