第2题 有序数组的合并2 查看测评数据信息 有N个正整数,前一半属于a数组,后一半属于b数组,a,b数组都为从小到大排序的数组,要求把两个数组合并,并使新的数组仍然是有序的,输出新数组。 输入格式 第一行1个正整数:N,范围在[1,8000000]。 第二行N个可以相同的正整数:范围在[1,8000000]。
时间: 2025-06-25 18:06:04 浏览: 12
### 实现两个有序数组的合并
对于给定的任务,目标是将两个已经排序好的数组 `nums1` 和 `nums2` 合并成一个新的有序数组。由于题目提到的大规模数据需求(N 范围在 1 到 8000000),因此需要考虑时间复杂度和空间效率。
以下是基于双指针法的一种高效解决方案:
#### 双指针方法描述
通过维护两个指针分别指向两个数组的起始位置,逐步比较当前指针所指向的元素大小,并按顺序填充到新数组中。这种方法的时间复杂度为 O(m+n),其中 m 和 n 分别代表两个数组的长度[^1]。
#### Python代码实现
下面提供了一个高效的 Python 实现方案,适用于大规模数据场景:
```python
def merge_sorted_arrays(nums1, m, nums2, n):
result = []
i, j = 0, 0
while i < m and j < n:
if nums1[i] <= nums2[j]:
result.append(nums1[i])
i += 1
else:
result.append(nums2[j])
j += 1
# 将剩余部分追加至结果列表
while i < m:
result.append(nums1[i])
i += 1
while j < n:
result.append(nums2[j])
j += 1
return result
# 输入样例
m = 5
n = 3
nums1 = [1, 3, 5, 7, 9]
nums2 = [2, 4, 6]
merged_array = merge_sorted_arrays(nums1[:m], m, nums2, n)
print(merged_array)
```
此代码片段展示了如何利用双指针技术来完成两组升序排列的数据合并操作[^2]。
另外,在某些情况下可以直接修改原数组而不创建额外的结果集。例如 Java 版本中的做法就是先复制再整体排序[^3]。然而当面对非常大的输入量时,这种策略可能因为频繁调用内置排序函数而显得不够理想;相比之下,采用手动控制逻辑的方式能够更好地优化性能表现。
阅读全文