algorithm - 给定两个排序列表，如何找到出现在 list1 但不在 list2 中的元素？

Question

我在面试中被问到这个问题。

例如，如果给定 list1: 1,1,2,4,5,7 和 list2: 1,3,5,8 我们应该返回一个 list3: 2,4,7.

这个问题需要的空间是常量，我们需要尽可能的降低时间复杂度。

Answer 1

我们只是同时遍历两个列表——使用两个“指针”进入它们——比较当前的两个元素。

• 当第一个列表的当前元素小于第二个列表的当前元素时，我们在结果的末尾复制第一个列表的当前元素并推进第一个指针。

• 当第一个列表的当前元素大于第二个列表的当前元素时，我们推进第二个指针。

• 当它们相等时，我们推进第一个指针。

当第一个指针到达列表末尾时停止。如果第二个指针首先执行此操作，则还要在 result 的末尾逐个复制 list1 中的所有剩余元素，或者 - 如果这些是 singly linked lists 并且允许共享结构——将结果的结束指针指向第一个指针的值。

假设 result 是一个链表，或者其他具有 O(1) add-at-end 操作的数据结构，这给出我们的复杂度为 O(n+m)，其中 n、m 是两个列表的长度。

此操作也称为 list1\list2 或 list2 相对于 list1 的 relative set complement。

使用的两个指针构成了算法使用的常量辅助空间。