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月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
2月前
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
16 2
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
24 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
16 0
|
2月前
|
算法 C++
Leetcode第59题(螺旋矩阵2)
这篇文章介绍了解决LeetCode第59题“螺旋矩阵II”的算法,通过C++编程实现按顺时针顺序填充一个n x n的正方形矩阵。
18 0
|
4月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
3月前
|
SQL Oracle 关系型数据库
CASE WHEN 语句的语法及示例,LeetCode 题目 “确认率” 练习
本文介绍了SQL中CASE语句的两种形式和语法,并通过LeetCode题目“确认率”的SQL查询示例展示了CASE语句在实际问题中的应用,解释了如何使用CASE语句计算特定条件的比率。
|
4月前
|
算法
LeetCode第74题搜索二维矩阵
文章讲解了LeetCode第74题"搜索二维矩阵"的解决方案,利用二分搜索法将问题简化,并通过数学转换找到二维矩阵中的对应元素,展示了将二维问题转化为一维问题的解题技巧。
LeetCode第74题搜索二维矩阵
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行