Java：如何检测ArrayList中的重复项？

Question

如何在Java中检测（返回true/false）一个ArrayList是否包含多个相同的元素？

非常感谢， Terry

编辑 忘记提到我不想将“块”与彼此进行比较，而是比较它们的整数值。 每个“块”都有一个int，这就是它们的不同之处。 通过调用名为“getNum”的方法（例如table1 [0] [2] .getNum（）;）可以找到特定块的int。

- Terry

---

如果“Block”是由int进行比较的，那么hashCode应该返回相同的int，并且equals应该比较这些int。 - Paul Tomblin

使用Set而不是List - dmarquina

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 */
}

更新：如果我正确理解你的问题，你有一个Block的2D数组，就像

Block table[][];

你想检测其中任何一行是否有重复项？

在这种情况下，我可以做如下操作，假设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
   }
}

对于语法，我并不能百分之百确定，所以最好写成以下形式更为安全

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

Set.add 如果添加的元素已经存在于集合中，返回一个布尔值 false。因此，如果你只想知道是否有重复项，甚至可以在返回 false 的任何添加操作上进行短路并退出。

- Paul Tomblin

---

请务必实现hashCode/equals方法。 - jon077

甚至更简单的方法是：在创建集合时进行包装，例如使用 new HashSet(list)，而不是使用 addAll。 - Fabian Steeg

@jon077：这取决于你对“重复”的定义。 - Michael Myers

如何将给定滑动窗口大小的数组列表进行处理，例如100个索引和滑动窗口大小为5？ 对于输入的ABCAD，应输出：ABCAD = 00010。如果下一个值是E，则BCADE应输出：00000。 - NIMISHAN

@NIMISHAN 请提出你自己的问题，不要试图劫持这个问题。 - Paul Tomblin

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;
}

- Adrian Kuhn

---

如果给定一个List参数，假设列表中不包含重复元素，那么告诉HashSet需要分配多少空间Set<T> set = new HashSet<T>(list.size());会更加高效。 - Paul Jackson

@PaulJackson 基于完整列表的大小可能会更有利。但是，如果通常情况下它早期找到重复项，则该空间将被浪费。此外，即使将HashSet的大小调整为列表的大小，由于哈希结构的基础负载因子，在运行整个列表时也会导致重新调整大小。 - Jay Anderson

除非您在运行时或空间方面遇到实际问题，否则我不会像那样微调您的代码。最好避免过早优化。 - akuhn

Answer 3

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

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

- Sergiy Dakhniy

Answer 4

如果您希望完全避免重复项，那么您应该削减掉检测重复的中间过程，而使用Set集合。

- matt b

---

请确保实现hashCode/equals :) - jon077

@jon077：不一定，就像我刚才说的那样。 - Michael Myers

然而，使用Set不会“检测”重复项，它只是防止它们出现。当然，除非你像@akuhn上面所指出的那样检查add方法的结果。 - mcallahan

Answer 5

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

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

---

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;
}

- user60062

---

这真的很棒。你有一些无效的代码，也许不是最优的方式，但你的方法绝对很棒！（而且它运行得很好） - Jules Colle

Answer 6

我需要对一个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());

- Jay Anderson

---

可以更简洁一些： return stream.allMatch(new HashSet<>()::add);，意思是检查stream中的所有元素是否都可以被添加到一个新的HashSet中。 - Jezor

Answer 7

如果您的元素在某种程度上是可比较的（事实上顺序是否有任何真正的意义并不重要——它只需要与您定义的相等性一致即可），最快的去重解决方案将对列表进行排序（0(n log(n))），然后进行单次遍历并查找重复元素（即，相互跟随的相等元素）（这是O(n)）。

总体复杂度将是O(n log(n))，这基本上与Set（n times long(n)）得到的复杂度相同，但常数要小得多。这是因为排序/去重中的常数来自于比较元素的成本，而来自于集合的成本很可能是哈希计算加上一个（可能是多个）哈希比较。如果您使用的是基于哈希的Set实现，那是因为基于树的实现会给您提供一个O(n log²(n))，这甚至更糟糕。

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

- Varkhan

---

在这种情况下，n为6，因此我不会在实现细节上浪费很多时间，但如果我需要做类似的事情，我会记住您的特殊堆排序算法的想法。 - Paul Tomblin

我不理解第三段。Mergesort和heapsort都是O(nlog(n))，而不是你所写的O(log(n))；即使你在识别到重复项后退出，这仍然不会改变你的时间复杂度... - ChaimKut

只是为了从互联网上删除混淆信息而进行评论。当使用插入到哈希集时，所接受答案的时间复杂度实际上是O(n)。内存复杂度加倍，但仍然是O(n)...除非您有最小化内存影响的要求，否则不需要对任何内容进行排序... - Petr Dvořák

Answer 8

如果您想要重复值的集合：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class FindDuplicateInArrayList {

    public static void main(String[] args) {

        Set<String> uniqueSet = new HashSet<String>();
        List<String> dupesList = new ArrayList<String>();
        for (String a : args) {
            if (uniqueSet.contains(a))
                dupesList.add(a);
            else
                uniqueSet.add(a);
        }
        System.out.println(uniqueSet.size() + " distinct words: " + uniqueSet);
        System.out.println(dupesList.size() + " dupesList words: " + dupesList);
    }
}

根据您的情况，可能需要考虑修剪值或使用小写字母。

- Saurabh

---

如果你想要重复项，最简单和最好的答案是使用uniqueSet提示来初始化args的大小以提高性能。 - Christophe Roussy

Answer 9

要查找列表中的重复项，请使用以下代码：它将返回包含重复项的集合。

 public Set<?> findDuplicatesInList(List<?> beanList) {
    System.out.println("findDuplicatesInList::"+beanList);
    Set<Object> duplicateRowSet=null;
    duplicateRowSet=new LinkedHashSet<Object>();
            for(int i=0;i<beanList.size();i++){
                Object superString=beanList.get(i);
                System.out.println("findDuplicatesInList::superString::"+superString);
                for(int j=0;j<beanList.size();j++){
                    if(i!=j){
                         Object subString=beanList.get(j);
                         System.out.println("findDuplicatesInList::subString::"+subString);
                         if(superString.equals(subString)){
                             duplicateRowSet.add(beanList.get(j));
                         }
                    }
                }
            }
            System.out.println("findDuplicatesInList::duplicationSet::"+duplicateRowSet);
        return duplicateRowSet;
  }

- Rakesh Sabbani

Answer 10

处理这个问题的最佳方法是使用一个HashSet：

ArrayList<String> listGroupCode = new ArrayList<>();
listGroupCode.add("A");
listGroupCode.add("A");
listGroupCode.add("B");
listGroupCode.add("C");
HashSet<String> set = new HashSet<>(listGroupCode);
ArrayList<String> result = new ArrayList<>(set);

只需打印结果arraylist并查看结果，不包含重复项 :)

- Ashana.Jackol