Skip to content

240 search a 2d matrix ii

240. Search a 2D Matrix II

题目: https://leetcode.com/problems/search-a-2d-matrix-ii/

难度: Medium

思路:

每行,每列都是sorted

但是比较好的策略是从右上角开始搜索,比如这样:

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]
]

m, n =  0, col - 1
更新策略:
 matrix[m][n] < target: 那么这一行到从左走到此都会小于target,row+1 ,往下走
 matrix[m][n] > target:  那么这一列往下走都会大于target,col - 1,往左走
 否则找到

时间复杂度O(max(M,N)),因为每次都会往下或者往左走

用的算法是Saddleback

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



回到顶部