作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、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
方法一:二分查找
解题步骤
- 将二维矩阵映射为一维数组:利用矩阵行列的关系,将二维索引转换为一维索引进行二分查找。
- 计算一维索引对应的行和列:一维索引
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))),其中
m
和n
是矩阵的行数和列数。 - 空间复杂度:(O(1)),不使用额外空间。
方法二:逐行二分查找
解题步骤
- 遍历每一行:对矩阵的每一行使用二分查找。
- 应用二分查找:在每一行中应用二分查找算法查找目标值。
完整的规范代码
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)),不需要额外空间。
方法三:分块查找
解题步骤
- 分块:将矩阵视为多个块,每个块是一行。
- 分块二分查找:对每个块应用二分查找。
完整的规范代码
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)),使用固定的空间。
方法四:逐行查找
解题步骤
- 逐行查找:遍历每一行,对每一行使用线性搜索。
- 线性搜索:在每行中线性地查找目标值。
完整的规范代码
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)),不使用额外空间。
方法五:对角线查找
解题步骤
- 对角线遍历:从矩阵的右上角开始,根据目标值与当前值的比较决定是向左移动还是向下移动。
- 对角线移动:如果当前值大于目标值,则向左移动;如果当前值小于目标值,则向下移动。
完整的规范代码
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)) |
优势 | 高效,适用于大矩阵 | 针对行有序的优化 | 快速且直观 | 简单易实现 | 从右上角开始,直观 |
劣势 | 需要理解一维映射 | 多次二分查找 | 需要理解移动规则 | 效率较低 | 需要理解移动逻辑 |
应用示例
数据库查询优化:在处理类似矩阵的数据结构时,如数据库表或二维数据集,使用这些算法可以优化查询操作,特别是在数据有序时。
游戏开发:在游戏开发中,可以使用这些技术来优化空间搜索,例如寻路算法或在网格上快速定位目标。
机器学习:在机器学习数据预处理阶段,这些方法可以用于快速处理和筛选特征矩阵,尤其是在进行特征选择和异常检测时。
欢迎关注微信公众号 数据分析螺丝钉