查找出现在一组列表中的所有数字

Question

我有几个Integer对象的ArrayLists，存储在一个HashMap中。

我想获得每个列表中出现的所有数字（整数对象）的列表（ArrayList）。

我的想法到目前为止是：

1. 迭代通过每个ArrayList和把所有的值到一个HashSet
   • 这将会给我们一个在列表中的所有值“上市”，但只有一次
2. 迭代通过HashSet的
   2.1随着每次迭代执行ArrayList.contains（）
   2.2如果没有任何ArrayLists为操作返回false，则将该数字添加到包含所有最终值的“主列表”中。

如果你能想出更快或更高效的东西，有趣的是我写这篇文章的时候提出了一个相当好的解决方案。但我仍会发布它，以防万一它对其他人有用。

但当然，如果你有更好的方法，请让我知道。

Answer 1

1. 从第一List创建Set（例如HashSet）。
2. 对于每个剩余列表：
   • 呼叫set.retainAll (list)如果两个list和set足够小
   • 否则调用set.retainAll (new HashSet <Integer> (list))

我不能说后阈值步骤2中的第二个变体。变得更快，但我猜可能是> 20大小左右。如果你的名单都很小，你不会打扰这个检查。

正如我记得Apache集合具有更有效的整数结构，如果你不仅关心O（*）部分，而且关于该因素。

Answer 2

你必须改变第1步： - 用最短的名单，而不是你的HashSet（如果不是在最短的名单是不是在所有列表...）

然后调用包含其他列表，并尽快删除值作为一个返回false（并且跳过这个值进一步的测试）

在结束时最短列表将包含答案...

一些代码：

public class TestLists { 

    private static List<List<Integer>> listOfLists = new ArrayList<List<Integer>>(); 

    private static List<Integer> filter(List<List<Integer>> listOfLists) { 

     // find the shortest list 
     List<Integer> shortestList = null; 
     for (List<Integer> list : listOfLists) { 
      if (shortestList == null || list.size() < shortestList.size()) { 
       shortestList = list; 
      } 
     } 

     // create result list from the shortest list 
     final List<Integer> result = new LinkedList<Integer>(shortestList); 

     // remove elements not present in all list from the result list 
     for (Integer valueToTest : shortestList) { 
      for (List<Integer> list : listOfLists) { 
       // no need to compare to itself 
       if (shortestList == list) { 
        continue; 
       } 

       // if one list doesn't contain value, remove from result and break loop 
       if (!list.contains(valueToTest)) { 
        result.remove(valueToTest); 
        break; 
       } 
      } 
     } 

     return result; 
    } 


    public static void main(String[] args) { 
     List<Integer> l1 = new ArrayList<Integer>(){{ 
      add(100); 
      add(200); 
     }}; 
     List<Integer> l2 = new ArrayList<Integer>(){{ 
      add(100); 
      add(200); 
      add(300); 
     }}; 
     List<Integer> l3 = new ArrayList<Integer>(){{ 
      add(100); 
      add(200); 
      add(300); 
     }}; 
     List<Integer> l4 = new ArrayList<Integer>(){{ 
      add(100); 
      add(200); 
      add(300); 
     }}; 
     List<Integer> l5 = new ArrayList<Integer>(){{ 
      add(100); 
      add(200); 
      add(300); 
     }}; 
     listOfLists.add(l1); 
     listOfLists.add(l2); 
     listOfLists.add(l3); 
     listOfLists.add(l4); 
     listOfLists.add(l5); 
     System.out.println(filter(listOfLists)); 

    } 

} 

Answer 3

我不确定我了解你的目标。但是，如果你想找到列表<整数>对象的集合的交集，那么你就可以做到以下几点：

public static List<Integer> intersection(Collection<List<Integer>> lists){ 
    if (lists.size()==0) 
     return Collections.emptyList(); 

    Iterator<List<Integer>> it = lists.iterator(); 
    HashSet<Integer> resSet = new HashSet<Integer>(it.next()); 
    while (it.hasNext()) 
     resSet.retainAll(new HashSet<Integer>(it.next())); 

    return new ArrayList<Integer>(resSet); 
} 

此代码在项目总数线性时间运行。实际上这是平均线性时间，因为使用了HashSet。

此外，请注意，如果您在循环中使用ArrayList.contains（），它可能会导致二次复杂性，因为此方法在线性时间内运行，不像HashSet.contains（）在恒定时间内运行。

Answer 4

使用谷歌收藏Multiset使这（代表明智）cakewalk（虽然我也喜欢Eyal's answer）。这可能不像其他人的时间/记忆方式那样有效，但是很清楚发生了什么。

假设列表包含本身内没有重复：

Multiset<Integer> counter = HashMultiset.create(); 
int totalLists = 0; 
// for each of your ArrayLists 
{ 
counter.addAll(list); 
totalLists++; 
} 

List<Integer> inAll = Lists.newArrayList(); 

for (Integer candidate : counter.elementSet()) 
    if (counter.count(candidate) == totalLists) inAll.add(candidate);` 

如果名单可能包含重复的元素，它们可以通过一组第一传递：

counter.addAll(list) => counter.addAll(Sets.newHashSet(list)) 

最后，这也是理想如果你想以后可能需要一些额外的数据（比如，某些特定的价值是如何接近的）。

另一种方法略微修改的Eyal的（基本上折叠在一起通过一组过滤列表，然后保持所有重叠元素的动作），并且比以上更轻巧：

public List<Integer> intersection(Iterable<List<Integer>> lists) { 

Iterator<List<Integer>> listsIter = lists.iterator(); 
if (!listsIter.hasNext()) return Collections.emptyList(); 
Set<Integer> bag = new HashSet<Integer>(listsIter.next()); 
while (listsIter.hasNext() && !bag.isEmpty()) { 
    Iterator<Integer> itemIter = listsIter.next().iterator(); 
    Set<Integer> holder = new HashSet<Integer>(); //perhaps also pre-size it to the bag size 
    Integer held; 
    while (itemIter.hasNext() && !bag.isEmpty()) 
    if (bag.remove(held = itemIter.next())) 
    holder.add(held); 
    bag = holder; 
} 
return new ArrayList<Integer>(bag); 
}