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

Question

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

我想获取每个列表中出现的所有数字(Integer 对象)的列表(ArrayList)。

目前我的想法是:

1. 遍历每个 ArrayList 并将所有值放入 HashSet
   • 这将为我们提供列表中所有值的“列表”，但只有一次
2. 遍历 HashSet
   2.1 每次迭代执行 ArrayList.contains()
   2.2 如果没有一个 ArrayLists 为操作返回 false，则将数字添加到包含所有最终值的“主列表”。

如果您能想出更快或更高效的方法，有趣的是，在我写这篇文章时，我想出了一个相当不错的解决方案。但我仍然会发布它，以防它对其他人有用。

当然，如果您有更好的方法，请告诉我。

Answer 1

我不确定我是否理解您的目标。但是，如果您希望找到 List 对象集合的 交集，则可以执行以下操作:

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() 不同。