在 Java 中查找 N 个列表之间的公共元素

Question

我需要编写一个 Java 程序来查找任意数量的列表或整数数组（任意长度）的交集（公共元素）。我想 Java 列表可能有一个有用的方法来实现这一点，但我正在查看 API 并找不到它。

有什么提示吗？

Answer 1

您可以尝试使用此方法查找 intersection/common -

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 2

您可以通过将一个列表的元素复制到一个新列表并使用 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 3

您可以使用属于 Java Collections class:

的 retainAll() 方法

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>();
list2.add(2);
list2.add(3);
list2.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都是长度n的ArrayList，a.retainAll(b)的时间复杂度是O(n^2)。如果在循环中使用 a.retainAll(b)，生成的算法很快就会变得完全不切实际。

另一种解决方案是将 ArrayList 转换为 HashSet。 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()) 以便算法在发现交叉点为空时立即停止。

在 Java 中查找 N 个列表之间的公共元素

Finding the common elements between N lists in Java

java

arrays

list

collections

intersection