已知 A,B 和 C 为三个递增有序的线性表,现要求对 A 表作如下操作:删去那些既在 B 表中出现又在 C 表中出现的元素。试对顺序表编写实现上述操作的算法,并分析你的算法的时间复杂度(注意:题中没 有特别指明同一表中的元素值各不相同
时间: 2023-03-19 14:22:38 浏览: 293
已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)
算法思路:
为了实现对 A 表的操作,我们可以采用双指针的方法。我们用两个指针 i 和 j 分别指向 A 表和 B 表,然后在 B 表中寻找 A 表中的元素,如果找到了,则在 C 表中寻找该元素,如果也找到了,则将该元素从 A 表中删除。最后返回修改后的 A 表。
算法实现:
```
def remove_common_elements(A, B, C):
i = 0
j = 0
while i < len(A) and j < len(B):
if A[i] == B[j]:
if A[i] in C:
A.pop(i)
else:
i += 1
j += 1
elif A[i] < B[j]:
i += 1
else:
j += 1
return A
```
算法分析:
该算法的时间复杂度为 O(n),其中 n 为 A 表的长度。因为算法的主要操作是在 A 表中查找元素,而 A 表是有序的,因此可以使用双指针的方法,将时间复杂度降低到线性级别。在查找元素的过程中,我们最多需要遍历 A 表一次,因此算法的时间复杂度为 O(n)。
阅读全文