Leetcode 240. Search a 2D Matrix II

发表于 | 分类于

问题描述

Write an efficient algorithm that searches for a value in an m x n 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.

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, return true.

Given target = 20, return false.

解题思路

先找到 target 可能在的行，然后在行内使用二分查找。

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
27
28
29
30
31
32
33
class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix:
            return False
        elif not matrix[0]:
            return False
        def binary_search(nums, target):
            l = 0
            r = len(nums) - 1
            while(l <= r):
                m = (l + r) // 2
                if nums[m] == target:
                    return True
                elif nums[m] < target:
                    l = m + 1
                else:
                    r = m - 1
            return False
        l = 0
        r = len(matrix)
        for nums in matrix:
            if nums[0] > target:
                return False
            if nums[-1] < target:
                continue
            if binary_search(nums, target):
                return True
        return False

进阶

对整个矩阵进行二分查找，或者进行分块儿查找。首先看整个矩阵 ((0, 0), (m-1, n-1))，中点 ((m-1)//2, (n-1)//2) 通过对比中点数据大小和target大小，确定target在哪个区域。

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
class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        X = [(0, 0, m - 1, n - 1)]
        while X:
            i, j, k, l = X.pop()
            if i > k or j > l or \
                matrix[i][j] > target or matrix[k][l] < target:
                continue
            p, q = (i + k)// 2, (j + l) // 2
            if matrix[p][q] == target:
                return True
            if matrix[p][q] < target:
                X += [(p + 1, j, k, q), (0, q + 1, k, l)]
            else:
                X += [(i, j, k, q - 1), (0, q, p - 1, l)]
        return False

Python耍赖做法

1
2
3
4
5
6
7
8
class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        return any(target in row for row in matrix)