在两个排序列表中查找匹配项比使用 for 循环更好的方法?
我有两个排序列表，都是非递减顺序.例如，我有一个带有元素 [2,3,4,5,6,7...] 的排序链表，另一个带有元素 [5,6,7,8,9...].
I have two sorted lists, both in non-decreasing order. For example, I have one sorted linked list with elements [2,3,4,5,6,7...] and the other one with elements [5,6,7,8,9...].
我需要在两个列表中找到所有共同的元素.我知道我可以使用 for 循环和嵌套循环来迭代所有匹配项以找到相同的两个元素.但是，是否有另一种运行时间小于 O(n^2) 的方法?
I need to find all common elements in both lists. I know I can use a for loop and a nested loop to iterate all matches to find the same two elements. However, is there another way to do this that has running time less than O(n^2)?
推荐答案
你可以在 O(n) 时间内完成.伪代码:
You can do it in O(n) time. Pseudocode:
a = list1.first
b = list2.first
repeat:
if a == b:
output a
a = list1.next
b = list2.next
elif a < b:
a = list1.next
else
b = list2.next
until either list has no more elements
相关文章