Java:检测ArrayList中的重复项？

如果你想避免重复,那么你应该删除检测重复项的中间过程并使用Set.

改进了返回重复元素的代码

可以在Collection中找到重复项

返回重复的集合

可以从Set中获取唯一元素

public static  List getDuplicate(Collection list) {

    final List duplicatedObjects = new ArrayList();
    Set set = new HashSet() {
    @Override
    public boolean add(T e) {
        if (contains(e)) {
            duplicatedObjects.add(e);
        }
        return super.add(e);
    }
    };
   for (T t : list) {
        set.add(t);
    }
    return duplicatedObjects;
}


public static  boolean hasDuplicate(Collection list) {
    if (getDuplicate(list).isEmpty())
        return false;
    return true;
}

如果你的元素在某种程度上是可比较的(订单有任何实际意义的事实是无关紧要的 - 它只需要与你的相等定义一致),最快的重复删除解决方案将对列表进行排序(0(n log( n)))然后进行单次传递并查找重复的元素(即,相互跟随的相等元素)(这是O(n)).

总体复杂度将是O(n log(n)),这与使用Set(n倍长(n))得到的大致相同,但具有更小的常量.这是因为sort/dedup中的常量来自比较元素的成本,而来自集合的成本最有可能来自散列计算,加上一个(可能是几个)散列比较.如果你正在使用基于散列的Set实现,也就是说,因为基于树的将给你一个O(nlog²(n)),这更糟糕.

但是,据我所知,你不需要删除重复项,而只是测试它们的存在.所以你应该在你的数组上手动编写一个合并或堆排序算法,如果你的比较器返回0,它只是退出返回true(即"有一个dup"),否则完成排序,并遍历排序的数组测试重复.实际上,在合并或堆排序中,当排序完成时,您将比较每个重复对,除非这两个元素已经位于其最终位置(这是不可能的).因此,调整排序算法应该会产生巨大的性能提升(我必须证明这一点,但我想调整后的算法应该在O(log(n))上的均匀随机数据上)

我需要为a做一个类似的操作Stream,但找不到一个好的例子.这就是我想出来的.

public static  boolean areUnique(final Stream stream) {
    final Set seen = new HashSet<>();
    return stream.allMatch(seen::add);
}

这具有短路的优点,即在早期发现重复时而不是必须处理整个流并且并不比仅仅将所有内容放入Set并检查大小复杂得多.所以这种情况大致是:

List list = ...
boolean allDistinct = areUnique(list.stream());