已知两个递增有序的顺序表La和Lb。编写算法将La和Lb合并成一个递减有序的顺序表,并将合并结果存放在La中,(假设表La空间足够大,不会溢出)。要求,时间复杂度为O(n)
时间: 2024-05-15 22:19:29 浏览: 147
数据结构实验报告-线性表-两个有序线性表的归并算法
5星 · 资源好评率100%
算法思路:
1. 定义指针i、j、k,分别表示La、Lb、合并后的新表中当前处理的元素下标。
2. 将i指向La中最后一个元素,j指向Lb中最后一个元素,k指向La中空闲位置的最后一个元素。
3. 从后往前遍历La和Lb,比较i和j指向的元素大小,将较大的元素存入La的空闲位置中,同时将对应的指针向前移动。
4. 如果La和Lb还有剩余元素,将剩余元素依次存入La中。
时间复杂度为O(n),n为La和Lb的总元素个数。
Python代码实现:
```python
def merge(La, Lb):
i, j, k = len(La) - 1, len(Lb) - 1, len(La) + len(Lb) - 1
while i >= 0 and j >= 0:
if La[i] < Lb[j]:
La[k] = La[i]
i -= 1
else:
La[k] = Lb[j]
j -= 1
k -= 1
while j >= 0:
La[k] = Lb[j]
j -= 1
k -= 1
# 示例
La = [1, 3, 5, 7, 9]
Lb = [2, 4, 6, 8, 10]
merge(La, Lb)
print(La) # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
```
阅读全文