LeetCode 题目 88:双指针\直接\递归\插入排序\归并排序 实现合并两个有序数组

简介: LeetCode 题目 88:双指针\直接\递归\插入排序\归并排序 实现合并两个有序数组

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

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

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

作者专栏每日更新:

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

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

python源码解读

程序员必备的数学知识与应用

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

题目描述

给定两个有序整数数组 nums1nums2,将 nums2 合并到 nums1 中,使得 nums1 成为一个有序数组。

初始化 nums1nums2 的元素数量分别为 mn。可以假设 nums1 有足够的空间(空间大小为 m + n)来保存 nums2 中的元素。

输入格式
  • nums1:第一个有序数组,长度为 m + n,后 n 个元素为 0,用于存放合并后的数组。
  • nums2:第二个有序数组,长度为 n
  • mnums1 中初始化的元素数量。
  • nnums2 中的元素数量。
输出格式
  • 直接在 nums1 上修改,无需返回值。

示例

示例 1
输入: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

方法一:直接合并后排序

解题步骤
  1. 合并数组:将 nums2 直接合并到 nums1 的末尾。
  2. 排序:对合并后的 nums1 进行排序。
完整的规范代码
def merge(nums1, m, nums2, n):
    """
    合并后直接排序
    :param nums1: List[int], 第一个有序数组
    :param m: int, nums1 的元素数量
    :param nums2: List[int], 第二个有序数组
    :param n: int, nums2 的元素数量
    """
    nums1[m:m+n] = nums2
    nums1.sort()
# 示例调用
nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)  # 输出: [1,2,2,3,5,6]
算法分析
  • 时间复杂度:(O((m+n) log (m+n))),排序操作的复杂度。
  • 空间复杂度:(O(1)),直接在输入数组上操作,不需要额外空间。

方法二:双指针从后向前

解题步骤
  1. 使用三个指针:分别指向 nums1nums2 的末尾,以及 nums1 合并后的末尾。
  2. 逆序合并:从后向前比较 nums1nums2,将较大的值放在合并后数组的末尾。
完整的规范代码
def merge(nums1, m, nums2, n):
    """
    双指针从后向前合并数组
    :param nums1: List[int], 第一个有序数组
    :param m: int, nums1 的元素数量
    :param nums2: List[int], 第二个有序数组
    :param n: int, nums2 的元素数量
    """
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
# 示例调用
nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)  # 输出: [1,2,2,3,5,6]
算法分析
  • 时间复杂度:(O(m+n)),每个元素最多处理一次。
  • 空间复杂度:(O(1)),直接在输入数组上操作。

方法三:递归合并

这是一个理论上的方法,不适用于这个问题,因为它不满足题目的空间要求,而且 Python 的递归也可能导致栈溢出。但为了完整性,这里给出思路:

解题步骤
  1. 递归基:如果 nums2 为空,递归结束。
  2. 递归合并:比较 nums1nums2 的最后一个元素,选择较大者放在最终位置,递归处理剩余数组。

由于 Python 默认的递归深度限制,以及递归方法通常需要额外的空间用于调用栈,这种方法并不适用于大数组或本题的要求。实际应用中应该避免使用递归方法处理这类问题。

方法四:插入排序思想

解题步骤
  1. 初始化:将 nums2 中的元素插入到 nums1 中合适的位置,确保 nums1 保持有序。
  2. 移动元素:为了插入元素,需要移动 nums1 中的元素以保持数组的有序性。
完整的规范代码
def merge(nums1, m, nums2, n):
    """
    使用插入排序的思想合并两个数组
    :param nums1: List[int], 第一个有序数组
    :param m: int, nums1 的元素数量
    :param nums2: List[int], 第二个有序数组
    :param n: int, nums2 的元素数量
    """
    for num in nums2:
        i = 0
        while i < m and nums1[i] < num:
            i += 1
        nums1[i+1:m+1] = nums1[i:m]  # 移动元素,为新元素腾出空间
        nums1[i] = num
        m += 1
# 示例调用
nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)  # 输出: [1,2,2,3,5,6]
算法分析
  • 时间复杂度:(O(m \times n)),每次插入操作平均需要移动 m/2 个元素,插入 n 次。
  • 空间复杂度:(O(1)),直接在输入数组上操作,不需要额外空间。

方法五:归并排序的合并阶段

解题步骤
  1. 使用额外数组:创建一个临时数组来存放合并的结果。
  2. 归并操作:像归并排序的合并阶段那样,从前向后比较两个数组的元素,将较小的元素先添加到临时数组中。
完整的规范代码
def merge(nums1, m, nums2, n):
    """
    使用归并排序的合并思想来合并两个有序数组
    :param nums1: List[int], 第一个有序数组
    :param m: int, nums1 的元素数量
    :param nums2: List[int], 第二个有序数组
    :param n: int, nums2 的元素数量
    """
    temp = []
    i, j = 0, 0
    while i < m and j < n:
        if nums1[i] < nums2[j]:
            temp.append(nums1[i])
            i += 1
        else:
            temp.append(nums2[j])
            j += 1
    # 处理剩余的元素
    while i < m:
        temp.append(nums1[i])
        i += 1
    while j < n:
        temp.append(nums2[j])
        j += 1
    # 将合并后的数组复制回 nums1
    nums1[:m+n] = temp
# 示例调用
nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)  # 输出: [1,2,2,3,5,6]
算法分析
  • 时间复杂度:(O(m+n)),每个元素只处理一次。
  • 空间复杂度:(O(m+n)),需要一个临时数组来存储合并后的结果。

不同算法的优劣势对比

特征 方法一:直接合并后排序 方法二:双指针从后向前 方法三:递归合并 方法四:插入排序思想 方法五:归并排序合并
时间复杂度 (O((m+n) \log (m+n))) (O(m+n)) (O(m \times n)) (O(m \times n)) (O(m+n))
空间复杂度 (O(1)) (O(1)) (O(m+n)) (O(1)) (O(m+n))
优势 简单易实现 最优时间复杂度,原地合并 保持原始方法逻辑,不实用 避免了排序,逐个插入 类似外部排序,清晰逻辑
劣势 时间较长,非最优解 需要注意边界条件 需要额外的空间,非原地操作 时间复杂度较高,不适用于大数据 需要额外空间,非原地操作

应用示例

这些方法在实际应用中非常有用,特别是在处理需要合并多个数据流或数据库查询结果时。例如,在数据库管理、日志文件处理和数据清洗等场景中,经常需要将多个有序数据流合并成一个有序的数据结构。这些技术能有效地优化这些操作。


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

相关文章
|
17天前
|
索引
力扣每日一题 6/17 枚举+双指针
力扣每日一题 6/17 枚举+双指针
11 1
|
20天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
11 1
|
5天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
1月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1月前
|
存储 算法
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(1)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题