从2个链表

Question

删除重复我在接受采访时被问到这个问题

LinkedList的一个具有{1,2,3,4,5,6}

LinkedList的B具有{1,3,5 }

我需要写这将返回回一组不包含在列表A和B的重复的元素

结果{2,4,6}

我写了一个解决的方法，它我可以吗对第一个列表进行terate，如果它不存在于第二个列表中，则将其添加到HashSet。但是需要一个比所建议的算法更好的解决方案。

为解决这个问题没有提到空间限制。

肯定会喜欢使用JDK，但我们更希望它是基于算法的解决方案

由于一吨

Answer 1

标准解决方案是循环遍历第一个列表，并将所有内容放入散列表中。这是线性时间，因为插入哈希表的时间是恒定的。

然后循环遍历第二个列表并查看每个元素是否存在于哈希表中。如果存在，请将其从表格中删除。否则，将此项目添加到新列表中。

现在将哈希表中剩下的所有内容都追加到新列表中。

这第二个操作也是线性的，因为哈希表的查找和删除也是常量。因此，整体算法是线性的。

Answer 2

在this blog post看看有各种removeAll()实现的分析解决方案

Answer 3

Integer[] a1 = {1,2,3,4,5,6}; 
    Integer[] a2 = {1,3,5,8}; 

    LinkedList<Integer> ll1 = new LinkedList(Arrays.asList(a1)); 
    LinkedList<Integer> ll2 = new LinkedList(Arrays.asList(a2)); 

    Set<Integer> set1 = new HashSet<Integer>(ll1); 
    Set<Integer> set2 = new HashSet<Integer>(ll2); 
    set1.removeAll(ll2); 
    set2.removeAll(ll1); 
    set1.addAll(set2); 

    System.out.println(set1); 

removeAll（）是subsrtaction和addAll（）是集合的联合。

Answer 4

这件事取决于你面试的位置。他们可能对你的逻辑感兴趣。其中一个可能的解决方案是从一个简单的方法：

public Set<Integer> killDuplicates(LinkedList<Integer> a0, LinkedList<Integer> a1) { 
     Set<Integer> common = new HashSet<Integer>(); 
     common.addAll(a0); //one could pass thru constructor, no matter 
     common.retainAll(a1); 
     Set<Integer> result = new HashSet<Integer>(); 
     result.addAll(a0); 
     result.addAll(a1); 
     result.removeAll(common); 
     return result; 
    } 

但还是这可能在某些情况下会明显变慢，并且有非常多的方法来改善这种代码的速度。 可能的解决方案之一是使用特殊结构进行快速设置交叉。

排序是不错的，但由于我们在LL它将使用归并排序数据（附加存储写的伪代码，但随时提问）：

public Set<Integer> killDuplicatesSorted(...) { 
    //sort a0 
    //sort a1 
    Iterator i0 = a0.getIterator(); 
    Iterator i1 = a1.getIterator(); 
    while (i0 != end && i1 != end) { 
     if (i0.current == i1.current) { 
      //skip presented in both 
      i0.moveNext(); 
      i1.moveNext(); 
     } else if (i0.current < i1.current) { 
      result.add(i0.current); 
      i0.moveNext(); 
     } else { 
      result.add(i1.current); 
      i1.moveNext(); 
     } 
    } 
    while (i0 != end) {result.add(i0.current); i0.moveNext();} 
    while (i1 != end) {result.add(i1.current); i1.moveNext();} 
    return result; 
} 

Answer 5

在Scala中，如前所述，使用内部映射，然后循环

scala> val x = (1 to 6).toList 
x: List[Int] = List(1, 2, 3, 4, 5, 6) 

scala> val y = (1 to 5 by 2).toList 
y: List[Int] = List(1, 3, 5) 

scala> val result = x.diff(y).toSet 
result: scala.collection.immutable.Set[Int] = Set(2, 4, 6)