作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、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)) |
| 优势 | 简单易实现 | 最优时间复杂度，原地合并 | 保持原始方法逻辑，不实用 | 避免了排序，逐个插入 | 类似外部排序，清晰逻辑 |
| 劣势 | 时间较长，非最优解 | 需要注意边界条件 | 需要额外的空间，非原地操作 | 时间复杂度较高，不适用于大数据 | 需要额外空间，非原地操作 |
应用示例
这些方法在实际应用中非常有用，特别是在处理需要合并多个数据流或数据库查询结果时。例如，在数据库管理、日志文件处理和数据清洗等场景中，经常需要将多个有序数据流合并成一个有序的数据结构。这些技术能有效地优化这些操作。
欢迎关注微信公众号 数据分析螺丝钉
