在两个排序列表中查找匹配项比使用 for 循环更好的方法? [英] Better way to find matches in two sorted lists than using for loops?

问题描述

我有两个排序列表，都是非递减顺序.例如，我有一个带有元素 [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

这篇关于在两个排序列表中查找匹配项比使用 for 循环更好的方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！