作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
python源码解读
程序员必备的数学知识与应用
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。可以假设 nums1 有足够的空间（空间大小为 m + n）来保存 nums2 中的元素。
输入格式
- nums1：第一个有序数组，长度为 m + n，后 n 个元素为 0，用于存放合并后的数组。
- nums2：第二个有序数组，长度为 n。
- m：nums1 中初始化的元素数量。
- n：nums2 中的元素数量。
输出格式
- 直接在 nums1 上修改，无需返回值。
示例
示例 1
输入: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
方法一：直接合并后排序
解题步骤
- 合并数组：将 nums2 直接合并到 nums1 的末尾。
- 排序：对合并后的 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))，直接在输入数组上操作，不需要额外空间。
方法二：双指针从后向前
解题步骤
- 使用三个指针：分别指向 nums1 和 nums2 的末尾，以及 nums1 合并后的末尾。
- 逆序合并：从后向前比较 nums1 和 nums2，将较大的值放在合并后数组的末尾。
完整的规范代码
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 的递归也可能导致栈溢出。但为了完整性，这里给出思路：
解题步骤
- 递归基：如果 nums2 为空，递归结束。
- 递归合并：比较 nums1 和 nums2 的最后一个元素，选择较大者放在最终位置，递归处理剩余数组。
由于 Python 默认的递归深度限制，以及递归方法通常需要额外的空间用于调用栈，这种方法并不适用于大数组或本题的要求。实际应用中应该避免使用递归方法处理这类问题。
方法四：插入排序思想
解题步骤
- 初始化：将 nums2 中的元素插入到 nums1 中合适的位置，确保 nums1 保持有序。
- 移动元素：为了插入元素，需要移动 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))，直接在输入数组上操作，不需要额外空间。
方法五：归并排序的合并阶段
解题步骤
- 使用额外数组：创建一个临时数组来存放合并的结果。
- 归并操作：像归并排序的合并阶段那样，从前向后比较两个数组的元素，将较小的元素先添加到临时数组中。
完整的规范代码
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)) 优势 简单易实现 最优时间复杂度，原地合并 保持原始方法逻辑，不实用 避免了排序，逐个插入 类似外部排序，清晰逻辑 劣势 时间较长，非最优解 需要注意边界条件 需要额外的空间，非原地操作 时间复杂度较高，不适用于大数据 需要额外空间，非原地操作 应用示例
这些方法在实际应用中非常有用，特别是在处理需要合并多个数据流或数据库查询结果时。例如，在数据库管理、日志文件处理和数据清洗等场景中，经常需要将多个有序数据流合并成一个有序的数据结构。这些技术能有效地优化这些操作。
- 直接在 nums1 上修改，无需返回值。