Sui Xin's Blog

[LeetCode]74. 搜索二维矩阵（Search a 2D Matrix）

Posted on In Disqus:

题目描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true

示例 2:

输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false

解题思路

二分法。主要是一个一维坐标到二维坐标的映射。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        if rows == 0:
            return False
        cols = len(matrix[0])
        if cols == 0:
            return False
        
        def get_idx(x):
            return x // cols, x % cols
        
        left, right = 0, rows * cols - 1
        while left < right:
            mid = (left + right) >> 1
            i, j = get_idx(mid)
            if matrix[i][j] < target:
                left = mid + 1
            else:
                right = mid
        final_i, final_j = get_idx(left)
        return matrix[final_i][final_j] == target

执行用时 : 92 ms
内存消耗 : 16 MB

Related Posts