LeetCode题目74:搜索二维矩阵

简介: LeetCode题目74:搜索二维矩阵

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

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

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。
输入格式
  • matrix:一个二维整数数组。
  • target:一个整数,表示需要查找的目标值。
输出格式
  • 返回一个布尔值,表示矩阵中是否存在目标值。

示例

示例 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

方法一:二分查找

解题步骤
  1. 将二维矩阵映射为一维数组:利用矩阵行列的关系,将二维索引转换为一维索引进行二分查找。
  2. 计算一维索引对应的行和列:一维索引 mid 可以映射回二维索引 matrix[mid // n][mid % n],其中 n 是矩阵的列数。
完整的规范代码
def searchMatrix(matrix, target):
    """
    使用二分查找判断矩阵中是否存在目标值
    :param matrix: List[List[int]], 输入的二维矩阵
    :param target: int, 需要查找的目标值
    :return: bool, 矩阵中是否存在目标值
    """
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    while left <= right:
        mid = (left + right) // 2
        mid_value = matrix[mid // n][mid % n]
        if mid_value == target:
            return True
        elif mid_value < target:
            left = mid + 1
        else:
            right = mid - 1
    return False
# 示例调用
print(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]], 3))  # 输出: True
print(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]], 13))  # 输出: False
算法分析
  • 时间复杂度:(O(\log(m \times n))),其中 mn 是矩阵的行数和列数。
  • 空间复杂度:(O(1)),不使用额外空间。

方法二:逐行二分查找

解题步骤
  1. 遍历每一行:对矩阵的每一行使用二分查找。
  2. 应用二分查找:在每一行中应用二分查找算法查找目标值。
完整的规范代码
def searchMatrix(matrix, target):
    """
    对矩阵的每一行进行二分查找
    :param matrix: List[List[int]], 输入的二维矩阵
    :param target: int, 需要查找的目标值
    :return: bool, 矩阵中是否存在目标值
    """
    n = len(matrix[0])
    for row in matrix:
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if row[mid] == target:
                return True
            elif row[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
    return False
# 示例调用
print(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]], 3))  # 输出: True
print(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]], 13))  # 输出: False
算法分析
  • 时间复杂度:(O(m \log n)),每行执行一次二分查找。
  • 空间复杂度:(O(1)),不需要额外空间。

方法三:分块查找

解题步骤
  1. 分块:将矩阵视为多个块,每个块是一行。
  2. 分块二分查找:对每个块应用二分查找。
完整的规范代码
def searchMatrix(matrix, target):
    """
    使用分块的方法查找矩阵中的目标值
    :param matrix: List[List[int]], 输入的二维矩阵
    :param target: int, 需要查找的目标值
    :return: bool, 矩阵中是否存在目标值
    """
    row, col = 0, len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return False
# 示例调用
print(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]], 3))  # 输出: True
print(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]], 13))  # 输出: False
算法分析
  • 时间复杂度:(O(m + n)),最坏情况下需要遍历矩阵的一行和一列。
  • 空间复杂度:(O(1)),使用固定的空间。

方法四:逐行查找

解题步骤
  1. 逐行查找:遍历每一行,对每一行使用线性搜索。
  2. 线性搜索:在每行中线性地查找目标值。
完整的规范代码
def searchMatrix(matrix, target):
    """
    使用逐行查找的方法查找矩阵中的目标值
    :param matrix: List[List[int]], 输入的二维矩阵
    :param target: int, 需要查找的目标值
    :return: bool, 矩阵中是否存在目标值
    """
    for row in matrix:
        if target in row:
            return True
    return False
# 示例调用
print(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]], 3))  # 输出: True
print(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]], 13))  # 输出: False
算法分析
  • 时间复杂度:(O(m \times n)),最坏情况下需要检查每个元素。
  • 空间复杂度:(O(1)),不使用额外空间。

方法五:对角线查找

解题步骤
  1. 对角线遍历:从矩阵的右上角开始,根据目标值与当前值的比较决定是向左移动还是向下移动。
  2. 对角线移动:如果当前值大于目标值,则向左移动;如果当前值小于目标值,则向下移动。
完整的规范代码
def searchMatrix(matrix, target):
    """
    使用对角线查找方法查找矩阵中的目标值
    :param matrix: List[List[int]], 输入的二维矩阵
    :param target: int, 需要查找的目标值
    :return: bool, 矩阵中是否存在目标值
    """
    if not matrix:
        return False
    row, col = 0, len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return False
# 示例调用
print(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]], 3))  # 输出: True
print(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]], 13))  # 输出: False
算法分析
  • 时间复杂度:(O(m + n)),可能需要遍历矩阵的一行或一列。
  • 空间复杂度:(O(1)),使用固定的空间。

不同算法的优劣势对比

特征 方法一:二分查找 方法二:逐行二分查找 方法三:分块查找 方法四:逐行查找 方法五:对角线查找
时间复杂度 (O(log(m * n))) (O(m log n)) (O(m + n)) (O(m * n)) (O(m + n))
空间复杂度 (O(1)) (O(1)) (O(1)) (O(1)) (O(1))
优势 高效,适用于大矩阵 针对行有序的优化 快速且直观 简单易实现 从右上角开始,直观
劣势 需要理解一维映射 多次二分查找 需要理解移动规则 效率较低 需要理解移动逻辑

应用示例

数据库查询优化:在处理类似矩阵的数据结构时,如数据库表或二维数据集,使用这些算法可以优化查询操作,特别是在数据有序时。

游戏开发:在游戏开发中,可以使用这些技术来优化空间搜索,例如寻路算法或在网格上快速定位目标。

机器学习:在机器学习数据预处理阶段,这些方法可以用于快速处理和筛选特征矩阵,尤其是在进行特征选择和异常检测时。

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
2月前
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
2月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
13天前
|
SQL Oracle 关系型数据库
CASE WHEN 语句的语法及示例,LeetCode 题目 “确认率” 练习
本文介绍了SQL中CASE语句的两种形式和语法,并通过LeetCode题目“确认率”的SQL查询示例展示了CASE语句在实际问题中的应用,解释了如何使用CASE语句计算特定条件的比率。
|
2月前
|
算法
LeetCode第74题搜索二维矩阵
文章讲解了LeetCode第74题"搜索二维矩阵"的解决方案,利用二分搜索法将问题简化,并通过数学转换找到二维矩阵中的对应元素,展示了将二维问题转化为一维问题的解题技巧。
LeetCode第74题搜索二维矩阵
|
2月前
|
算法
LeetCode第35题搜索插入位置
这篇文章介绍了LeetCode第35题"搜索插入位置"的解题方法,通过使用二分查找法,高效地找到在有序数组中插入一个目标数的最佳位置。
LeetCode第35题搜索插入位置
|
2月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组
|
2月前
|
算法
LeetCode第12题目整数转罗马数字
该文章介绍了 LeetCode 第 12 题整数转罗马数字的解法,通过使用 TreeMap 按照整数从大到小排序,先使用大的罗马数字表示整数,再用小的,核心是先表示完大的罗马数字,想通此点该题较简单。
LeetCode第12题目整数转罗马数字
|
2月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
40 6
|
2月前
|
算法
LeetCode第13题目罗马数字转整数
该文章介绍了 LeetCode 第 13 题罗马数字转整数的解法,通过从大到小解析罗马数字,根据罗马数字的特点,按照从大到小的顺序匹配罗马数字和整数的关系,从而解决该问题,同时强调要注意观察题目考查的知识点特征。