74. 搜索二维矩阵 [medium]

https://leetcode-cn.com/problems/search-a-2d-matrix/

编写一个高效的算法来判断 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

通过次数49,222 | 提交次数128,665

Second Try

2020-07-03

虚拟展开成一维数组，idx标号可以方便转化为m,n矩阵坐标。

看题解才想起还可以这么搞，之前在数独的题目中已经用过类似的了。

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        # 虚拟展开成一维数组，idx标号可以方便转化为m,n矩阵坐标
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        m, n = len(matrix), len(matrix[0])
        # 行坐标是[0, m-1]， 列坐标范围是[0, n-1]
        midx = lambda idx: divmod(idx, n)
        
        # 二分法开始
        left, right = 0, m * n - 1
        while left <= right:
            mid = left + (right - left) // 2
            r, c = midx(mid)
            if matrix[r][c] == target:
                return True
            elif matrix[r][c] > target:
                right = mid - 1
            elif matrix[r][c] < target:
                left = mid + 1
        return False 

执行用时：16 ms, 在所有 Python 提交中击败了95.68%的用户
内存消耗：13.6 MB, 在所有 Python 提交中击败了60.00%的用户

First Try

2020-07-03

通过左边界确定了行，然后再通过普通二分法确定列，是一个比较绕的写法，但复杂度跟上面的是一样的。lg(m) + lg(n) = lg(mn)

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        # 展平也算是O(N)了，所以还是得从最开始就用二分法LgN才行
        # 如果在某一行中，则改行第一个元素是left bound，第二行是right bound
        # todo:考虑matrix为空的情况
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        # 先确定一波在哪一行，这一行的起点必须小于target，但是下一行的起点必须大于target
        # 因此应该是在跳出循环后的right边界
        left, right = 0, len(matrix) - 1
        while left <= right:
            mid = (left + right) / 2
            if matrix[mid][0] < target:
                left = mid + 1
            elif matrix[mid][0] > target:
                right = mid - 1
            elif matrix[mid][0] == target:
                return True
        # print("phase one", left, right)
        # 不需要关心left，又贡献了一个bug...
        # if left >= len(matrix) or right < 0:
        if right < 0:
            return False
        row = right

        # 考虑在某一行里的所有元素，用普通的二分法就行了
        left, right = 0, len(matrix[0]) - 1  # 靠，差点又写成了right = len(matrx[0])
        # print("next phase", left, right, row)
        while left <= right:
            mid = (left + right) / 2
            if matrix[row][mid] < target:
                left = mid + 1
            elif matrix[row][mid] > target:
                right = mid - 1
            elif matrix[row][mid] == target:
                return True
        # print("end", left, right)
        return False

执行用时：20 ms, 在所有 Python 提交中击败了82.52%的用户
内存消耗：13.4 MB, 在所有 Python 提交中击败了100.00%的用户

74. 搜索二维矩阵 [medium]​

Second Try​

First Try​

74. 搜索二维矩阵 [medium]

Second Try

First Try