leetcode_240

发表于   |   分类于

Search a 2D Matrix II

题目戳这

题意

给定一个有序的n*m二维数组，二维数组从左至右是按从小到大排列，二维数组从上到下也是从小到大排列，给定一个数target，问你在这个二维数组中是否存在这个数字。

解法

我们只要看每个子矩阵的右上角的数字即可，如果该数字大于target，说明这个数字所在的列都是大于target的，去掉这一列，如果这个数字小于target，说明这个数字所在的行都是小于target的，去掉该行，最后如果能找到的话就返回true，否则返回false.复杂度为max(n,m).

代码

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(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix:
            return False
        m = len(matrix)
        n = len(matrix[0])
        
        row = 0
        col = n-1
        ans = False
        while row < m and col >=0:
            if matrix[row][col] == target:
                ans = True
                break
            if matrix[row][col] > target:
                col -= 1
            elif matrix[row][col] < target:
                row += 1
        
        return ans