查找Java中N個列表之間的通用元素

Question

我需要編寫一個Java程序來查找任意數量的列表或整數數組（任意長度）的交集（公共元素）。我猜Java列表可能有一個有用的方法來實現這一點，但我正在看看API並找不到它。

任何提示？

Answer 1

你可以找到兩個列表之間的共同之處一個列表到新列表中，並使用retainAll：

List<T> commonElements = new ArrayList<>(list1); 
commonElements.retainAll(list2); 

這可以擴展到n列表，因爲在n列表的公共元素是[第一n-1列表的公共元素]的共同元件和[所述n個列表的元素]：

commonElements.retainAll(list3); 
commonElements.retainAll(list4); 
... 

例如

<T> List<T> commonElements(Iterable<? extends List<? extends T>> lists) { 
    Iterator<? extends List<? extends T>> it = lists.iterator(); 
    List<T> commonElements = new ArrayList<T>(it.next()); 
    while (it.hasNext()) { 
    commonElements.retainAll(it.next()); 
    } 
    return commonElements; 
} 

請注意，如果列表爲空，則會失敗，並顯示NoSuchElementException。處理這種情況很簡單，在第一個it.next()之前加上一個it.hasNext()的檢查。

Answer 2

你可以試試這個方法找到交集/通用 -

public <T> List<T> common(List<T> list1, List<T> list2) { 
     List<T> commonList = new ArrayList<T>(); 

     for (T t : list1) { 
      if(list2.contains(t)) { 
       list.add(t); 
      } 
     } 


     return commonList; 
    } 

或者你可以使用retainAll()方法 - 通過複製的元素

list1.retainAll(list2); 

Answer 3

可以使用retainAll()方法是Java Collections類的一部分：

List<Integer> list1 = new ArrayList<Integer>(); 
list1.add(1); 
list1.add(2); 
list1.add(3); 
System.out.println("First list has elements: " + list1); 

List<Integer> list2 = new ArrayList<Integer>(); 
list1.add(2); 
list1.add(3); 
list1.add(4); 
System.out.println("Second list has elements: " + list2); 

list1.retainAll(list2); 
System.out.println("Intersection between the lists is: " + list1); 

如果需要彙總此對列表中的任意號碼，你可以簡單地調用list1.retainAll(listn)，其中listn是另一個List 。

輸出：

First list has elements: [1, 2, 3] 
Second list has elements: [2, 3, 4] 
Intersection between the lists is: [2, 3] 

Answer 4

你應該想到非常小心使用任何方法retainAll，removeAll或containsAll與ArrayList是因爲contains爲ArrayList之前有O(n)時間複雜度。如果a和b都是ArrayList，其長度爲n,a.retainAll(b)具有時間複雜度O(n^2)。如果在循環中使用a.retainAll(b)，則生成的算法很快變得完全不切實際。

另一種解決方案是將ArrayList s轉換爲HashSet s。 contains對於HashSet具有O(1)時間複雜度。

static <T> List<T> commonElements(Iterable<? extends List<? extends T>> lists) { 
    Iterator<? extends List<? extends T>> it = lists.iterator(); 
    Set<T> commonElements = new HashSet<>(it.next()); 
    while (it.hasNext()) 
     commonElements.retainAll(new HashSet<>(it.next())); 
    return new ArrayList<>(commonElements); 
} 

當然，如果有短List秒的數量少，在上面的代碼全部複製將使這個版本比@ AndyTurner的慢。您使用的版本取決於您的確切情況。

這些解決方案的另一個問題是它們如何處理多重性。假設第一個列表是[1, 1, 1]，第二個列表是[1, 1]。對這些列表的交集最合理的解釋是[1, 1]。不過，@ AndyTurner的版本將產生[1, 1, 1]，而上述版本將產生[1]。

這是一個正確處理多重性的版本。方法引用和Map.merge需要Java 8

static <T> List<T> commonElements(Iterable<? extends List<? extends T>> lists) { 
    Iterator<? extends List<? extends T>> iterator = lists.iterator(); 
    Map<T, Integer> multiplicities = count(iterator.next()); 
    while (iterator.hasNext()) { 
     Map<T, Integer> listCount = count(iterator.next()); 
     for (Iterator<Map.Entry<T, Integer>> it = multiplicities.entrySet().iterator(); it.hasNext();) { 
      Map.Entry<T, Integer> e = it.next(); 
      T key = e.getKey(); 
      Integer count = listCount.get(key); 
      if (count == null) 
       it.remove(); 
      else 
       e.setValue(Math.min(count, e.getValue())); 
     } 
    } 
    List<T> result = new ArrayList<>(); 
    for (Map.Entry<T, Integer> e : multiplicities.entrySet()) 
     result.addAll(Collections.nCopies(e.getValue(), e.getKey())); 
    return result; 
} 

private static <T> Map<T, Integer> count(List<? extends T> list) { 
    Map<T, Integer> result = new HashMap<>(); 
    for (T t : list) 
     result.merge(t, 1, Integer::sum); 
    return result; 
} 

您可以按如下步驟測試它

List<Integer> list1 = Arrays.asList(1, 1, 2, 2, 2, 3, 4); 
List<Integer> list2 = Arrays.asList(1, 1, 1, 2, 2, 3, 5); 
List<Integer> common = commonElements(Arrays.asList(list1, list2)); 
System.out.println(common); 

輸出：

[1, 1, 2, 2, 3] 

有很多方法來改善上述方法。例如，您可以首先處理最小的List，以使multiplicities儘可能小。同樣，在計算listCount之後，如果listCount較小，則可以交換listCount和multiplicities。您也可以將while替換爲while (!multiplicities.isEmpty() && iterator.hasNext())，以便在發現交點爲空時立即停止算法。