pythontip 100days-day22

Code › python
, ,

题目

在一个m*n的二维数组matrix中判断目标值target是否存在,该二维数组具有以下性质:

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

例子

searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]],3) -> True
searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]],13) -> False

假设

  1. 输入的二维数组不为空

tips

  1. 二分查找
  2. 一位坐标映射二维坐标

答案

解法1

def searchMatrix(matrix,target):
    m = len(matrix)
    n = len(matrix[0])
    left , right = 0 , m * n - 1
    while left <= right:
        pivot_idx = (left + right) // 2
        pivot_element = matrix[pivot_idx // n][pivot_idx % n]
        if target == pivot_element:
            return True
        else:
            if target < pivot_element:
                right = pivot_idx - 1
            else:
                left = pivot_idx + 1
    return False

性能：

  1. 时间复杂度O(logmn)
  2. 空间复杂度O(1)

关键点：

  1. 二分查找
  2. 一位坐标映射二维坐标

解法2：

def searchMatrix(matrix, target):
    """
    1. 找到tatget所在的列表
    2. 使用二分法判断
    :param matrix:
    :param target:
    :return:
    """
    if not matrix:
        return False
    for item in matrix:
        if item[0] <= target <= item[-1]:
            i, j = 0, len(item) - 1
            while i <= j:
                m = (i + j) // 2
                if item[m] == target:
                    return True
                elif item[m] < target:
                    j = m - 1
                else:
                    i = m + 1

            return False
        
    return False