查找出現在一組列表中的所有數字

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); 
}