我有两个整数的单链接列表。其中一个是另一个的子集（数字的顺序不同）。找到第一个列表包含而第二个列表不包含的数字的最佳方法（关于性能）是什么？
我的想法是首先对它们进行排序（使用合并排序），然后逐个元素进行比较。因此，它需要O(nlogn+mlogm+n)，但是O(n)应该有更好的解决方案。
这是时间和空间上的O（n）解决方案。
逻辑
假设原始链表的大小为N，我们将其称为LL1N ，第二链表的LL2大小为。
=>准备一个Hasmap大小为N的，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）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句