java - 如何在 O(n) 中找到两个链表之间缺少的元素？

Question

我有两个整数单链表。其中一个是另一个的子集(数字顺序不同)。找到第一个列表包含而第二个列表不包含的数字的最佳方法(关于性能)是什么？

我的想法是首先对它们进行排序(使用合并排序)，然后逐个元素进行比较。因此，它需要 O(nlogn+mlogm+n)，但应该存在更好的 O(n) 解决方案。

Answer 1

这在时间和空间上都是 O(n) 的解决方案。

逻辑

假设原始链表的大小为 N 我们将其称为 LL1 并且第二个链表为 LL2.

=> 准备一个大小为N的Hasmap，key就是中的numbers LL1 和 value 将是 LL2

中的频率

 HashMap<Integer,Integer> map= new HashMap<Integer,Integer>();

=> 开始遍历 LL1 并将所有数字的频率设置为 0
此时 LL1 中的所有值被迭代，您拥有 HashMap 中频率 = 0

的所有数字

 map.put(key, 0);

=> 现在开始遍历 LL2，使用它们作为键选择数字并将值增加 1。
当 LL2 中的所有值都被迭代时，您在 HashMap< 中的 LL1 和 LL1 中都存在所有常见数字 具有频率 > 0

  map.put(key, map.get(key) + 1);

=> 现在开始遍历hasmap，搜索value = 0，找到后打印key 因为这个数字只出现在 LL1 而不是 LL2

for (map.Entry<Integer,Integer> entry : map.entrySet())
{
    if(entry.getValue() == 0)
        System.out.println(entry.getKey());//This is a loner
}

2 次迭代和 O(n) 内存，时间为 O(n)。