java - 如何在O(n)的两个链​​接列表之间找到缺失的元素？

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

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

最佳答案

这是时间和空间上的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中的所有值都被迭代时，您在LL1中的LL1和HashMap中都存在所有通用数字frequency > 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)。

关于java - 如何在O(n)的两个链​​接列表之间找到缺失的元素？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26091882/