搜索二维矩阵

Search a 2D Matrix

专题: Algorithmic Programming / 算法编程
难度: L4
来源: QuantQuestion

题目详情

给定一个 $m\times n$ 的二维整数数组 matrix 和一个整数 target。

matrix 每行按非降序排序；
每行第一个元素都大于上一行最后一个元素。

若 target 存在于 matrix 中返回 true，否则返回 false。

能否写出时间复杂度为 $O(\log(mn))$ 的解法？

You are given an m x n 2-D integer array matrix and an integer target.

Each row in matrix is sorted in non-decreasing order. The first integer of every row is greater than the last integer of the previous row. Return true if target exists within matrix or false otherwise.

Can you write a solution that runs in O(log(m * n)) time?

Example 1:

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10

Output: true Example 2:

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15

Output: false Constraints:

m == matrix.length n == matrix[i].length 1 <= m, n <= 100 -10000 <= matrix[i][j], target <= 10000

解析

把矩阵视作长度为 $mn$ 的有序一维数组：下标 $k$ 对应的元素是 $matrix[\lfloor k/n\rfloor][k\bmod n]$ 。

对 $k\in[0,mn-1]$ 做二分查找即可，时间 $O(\log(mn))$ ，空间 $O(1)$ 。

Original Explanation


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])

        top, bot = 0, ROWS - 1
        while top <= bot:
            row = (top + bot) // 2
            if target > matrix[row][-1]:
                top = row + 1
            elif target < matrix[row][0]:
                bot = row - 1
            else:
                break

        if not (top <= bot):
            return False
        row = (top + bot) // 2
        l, r = 0, COLS - 1
        while l <= r:
            m = (l + r) // 2
            if target > matrix[row][m]:
                l = m + 1
            elif target < matrix[row][m]:
                r = m - 1
            else:
                return True
        return False