java - 找出两个排序列表是否包含相同元素 Java 的有效方法。

Question

我有一个搜索互素数的紧密循环。列表 primeFactors。它的第 n 个元素包含 n 的质数分解的排序列表。我正在使用 checkIfPrimes

检查 c 和 d 是否互素

boolean checkIfPrimes(int c, int d, List<List<Integer>> primeFactors) {
    List<Integer>  common = new ArrayList<>(primeFactors.get(d)); //slow
    common.retainAll(primeFactors.get(c));        
    return (common.isEmpty());
}

primeFactors.get(d).retainAll(primeFactors.get(c)) 看起来很有希望，但它会改变我的可重用 primeFactors 对象。

创建新对象相对较慢。有没有办法加快这一步？我能以某种方式利用列表已排序的事实吗？我应该改用数组吗？

Answer 1

您可以使用具有更快查找速度的Collection - 例如Set 如果您只需要没有重复的主要因素，或者 Map 如果您还需要每个因素的计数。

基本上，您想知道两个 Set 的交集是否为空。 Oracle Set tutorial显示了一种计算交集的方法(类似于您已经提到的，在副本上使用 retainAll，但在 Sets 上操作应该更有效)。