Java:检测ArrayList中的重复项？

Question

我怎样才能检测(返回true/false)ArrayList是否包含Java中的多个相同元素？

非常感谢,特里

编辑 忘了提到我不打算将"块"相互比较,但是它们的整数值.每个"块"都有一个int,这就是它们的不同之处.我通过调用名为"getNum"的方法找到特定块的int(例如table1 [0] [2] .getNum();

Answer 1

最简单:将整个集合转储到Set中(使用Set(Collection)构造函数或Set.addAll),然后查看Set是否与ArrayList具有相同的大小.

List<Integer> list = ...;
Set<Integer> set = new HashSet<Integer>(list);

if(set.size() < list.size()){
    /* There are duplicates */
}

更新:如果我正确理解你的问题,你有一个2d的Block数组,如

阻止表[] [];

并且你想检测它们中的任何一行是否有重复？

在这种情况下,假设Block正确实现"equals"和"hashCode",我可以执行以下操作:

for (Block[] row : table) {
   Set set = new HashSet<Block>(); 
   for (Block cell : row) {
      set.add(cell);
   }
   if (set.size() < 6) { //has duplicate
   }
}

我对语法并不是100%肯定,因此将其编写为更安全

for (int i = 0; i < 6; i++) {
   Set set = new HashSet<Block>(); 
   for (int j = 0; j < 6; j++)
    set.add(table[i][j]);
 ...

...

Answer 2

改进了代码,使用返回值Set#add而不是比较列表和集合的大小.

public static <T> boolean hasDuplicate(Iterable<T> all) {
    Set<T> set = new HashSet<T>();
    // Set#add returns false if the set does not change, which
    // indicates that a duplicate element has been added.
    for (T each: all) if (!set.add(each)) return true;
    return false;
}

Answer 3

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

Answer 4

使用 Java 8+，您可以使用 Stream API：

boolean areAllDistinct(List<Block> blocksList) {
    return blocksList.stream().map(Block::getNum).distinct().count() == blockList.size();
}

Answer 5

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

• 可以在Collection中找到重复项
• 返回重复的集合
• 可以从Set中获取唯一元素

public static <T> List getDuplicate(Collection<T> list) {

    final List<T> duplicatedObjects = new ArrayList<T>();
    Set<T> set = new HashSet<T>() {
    @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 <T> boolean hasDuplicate(Collection<T> list) {
    if (getDuplicate(list).isEmpty())
        return false;
    return true;
}

Answer 6

如果你的元素在某种程度上是可比较的(订单有任何实际意义的事实是无关紧要的 - 它只需要与你的相等定义一致),最快的重复删除解决方案将对列表进行排序(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))上的均匀随机数据上)

Answer 7

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

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

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

List<T> list = ...
boolean allDistinct = areUnique(list.stream());