两个递增有序的数组合并
时间: 2023-08-10 17:32:57 浏览: 96
可以使用归并排序的思想来合并两个递增有序的数组。具体步骤如下:
1. 定义两个指针i和j,分别指向两个数组的起始位置;
2. 定义一个新的数组result,用于存放合并后的结果;
3. 比较数组1和数组2中i和j位置上的元素大小,将较小的元素添加到result数组中,并将指针i或j向后移动一位;
4. 重复步骤3,直到任意一个数组的元素全部添加到result数组中;
5. 将另一个数组中剩余的元素添加到result数组中;
6. 返回result数组。
以下是Python实现代码:
```python
def merge_sorted_arrays(arr1, arr2):
i, j = 0, 0
m, n = len(arr1), len(arr2)
result = []
while i < m and j < n:
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
while i < m:
result.append(arr1[i])
i += 1
while j < n:
result.append(arr2[j])
j += 1
return result
# 示例
arr1 = [1, 3, 5, 7, 9]
arr2 = [2, 4, 6, 8, 10]
print(merge_sorted_arrays(arr1, arr2)) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
```
注意,以上实现假设两个输入数组已经是递增有序的。如果不是,则需要在合并前先对它们进行排序。
阅读全文