从ArrayList中删除重复值（两个值都要删除）

Question

我有一个包含以下字符串的 ArrayList;

 List<String> e = new ArrayList<String>();
 e.add("123");
 e.add("122");
 e.add("125");
 e.add("123");

我想检查列表中的重复项并将其从列表中删除。 在这种情况下，我的列表只有两个值，在此示例中它将是值122和125，而两个123将会消失。最好的方法是什么？我考虑使用一个Set，但那只会删除其中一个重复项。

- danilo

---

你可以使用一个Map<String，Integer>（表示String出现的次数），然后过滤掉只有值为1的条目，并将对应的键收集到一个新列表中。 - Alexis C.

@3Kings想要删除重复的值，因此在上面的例子中，两个123都应该被删除。 - Shadow Droid

set的add()方法返回true，如果该值没有重复并成功插入。您可以使用它来获取指示，以确定您要插入的新值是否为重复项。然后，您可以查找并删除重复项。 - svarog

你可以使用多重哈希映射。 - Jürgen K.

一个 Set 不会移除项目，它将防止添加重复的项目。 - Thomas Weller

Answer 1

在Java 8中，您可以执行：

e.removeIf(s -> Collections.frequency(e, s) > 1);

若不是Java 8，您可以创建一个HashMap<String, Integer>。如果该字符串已经出现在map中，则将其键值加一，否则将其添加到map中。

例如：

put("123", 1);

现在假设你再次拥有"123"，你应该获得该键的计数并将其加一：

put("123", get("aaa") + 1);

现在您可以轻松地在地图上进行迭代，并创建一个新的数组列表，其中键的值小于2。

参考资料：

• ArrayList#removeIf
• Collections#frequency
• HashMap

- Maroun

---

Java 8版本是可行的，但这仅限于ArrayList类型，因为removeIf被重写以在结尾时批量执行所有删除操作。例如，在LinkedList上它不起作用。 - Paul Boddington

List::removeIf 是一种简洁的解决方案，但由于需要遍历列表并使用 Collection::frequency ，其时间复杂度为 O(n²)，我的理解正确吗？ - Flown

查找重复项的复杂度为O(n²)，应用removeIf仅增加常数时间。因此，总体复杂度确实为O(n²)。 - Maroun

如果您创建了一个Map<String, Long>来计算出现次数，然后迭代EntrySet以获取唯一元素，则复杂度为O(2*n) -> O(n)，我理解的是否正确？ - Flown

@Taemyr 正确，但在我所知道的任何哈希映射实现中，m都是O(n)（我甚至可以说这是唯一合理的选择），因为容量会被调整为比当前大小大一些的分数。 - Voo

Answer 2

您也可以在Java 8中使用filter

e.stream().filter(s -> Collections.frequency(e, s) == 1).collect(Collectors.toList())

- Sajan Chandran

Answer 3

你可以使用一个 HashMap<String, Integer>。

你遍历列表，如果哈希映射不包含该字符串，则将其添加到哈希映射中并赋值为1。

如果哈希映射已经包含该字符串，则只需增加计数器即可。因此，该字符串的哈希映射如下所示：

{"123", 2}
{"122", 1}
{"125", 1}

您需要创建一个新列表，其中每个键的值都为1。

- npinti

Answer 4

这里是一个不使用Java 8的解决方案，使用map来计算出现的次数：

Map <String,Integer> map = new HashMap<String, Integer>();
for (String s : list){
    if (map.get(s) == null){
      map.put(s, 1);
    } 
    else {
      map.put(s, map.get(s) + 1);
    }
}

List<String> newList = new ArrayList<String>();

// Remove from list if there are multiples of them.
for (Map.Entry<String, String> entry : map.entrySet())
{
  if(entry.getValue() > 1){
    newList.add(entry.getKey());
  }
}

list.removeAll(newList);

- ergonaut

---

newList 添加了所有计数大于等于2的条目。这是一个临时列表。原始列表为 list，因此为了“返回 list”，我通过删除所有计数为1的条目来修改它。 - ergonaut

问题是删除计数大于等于2的那些。 - user253751

Answer 5

ArrayList中的解决方案

public static void main(String args[]) throws Exception {
      List<String> e = new ArrayList<String>();
      List<String> duplicate = new ArrayList<String>();
      e.add("123");
      e.add("122");
      e.add("125");
      e.add("123");

      for(String str : e){
          if(e.indexOf(str) != e.lastIndexOf(str)){
              duplicate.add(str);
          }
      }

      for(String str : duplicate){
          e.remove(str);              
      }

      for(String str : e){
          System.out.println(str);
      }
  }

- Android Developer

Answer 6

List<String> e = new ArrayList<String>();
e.add("123");
e.add("122");
e.add("125");
e.add("123");
e.add("125");
e.add("124");
List<String> sortedList = new ArrayList<String>();
for (String current : e){
    if(!sortedList.contains(current)){
        sortedList.add(current);
    }
    else{
        sortedList.remove(current);
    }
}
e.clear();
e.addAll(sortedList);

- Ray Lloy

Answer 7

使用流的最简单解决方案时间复杂度为O(n^2)，如果你在包含数百万条目的List上尝试它们，你将等待很长时间。一个O(n)的解决方案是:

list = list.stream()
           .collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()))
           .entrySet()
           .stream()
           .filter(e -> e.getValue() == 1)
           .map(Map.Entry::getKey)
           .collect(Collectors.toList());

在这里，我使用了一个LinkedHashMap来维护顺序。请注意，静态导入可以简化collect部分。

这么复杂的问题，我认为使用for循环是最好的选择。

Map<String, Integer> map = new LinkedHashMap<>();
for (String s : list)
    map.merge(s, 1, Integer::sum);
list = new ArrayList<>();
for (Map.Entry<String, Integer> e : map.entrySet())
    if (e.getValue() == 1)
        list.add(e.getKey());

- Paul Boddington

---

流复杂度也是O(2*n)，因此为O(n)。 - Flown

@Flown 它表示 O(n)。 - Paul Boddington

@Flown 我并不是。它说使用流的最简单解决方案是O(n^2)。而我的解决方案并不是最简单的。 - Paul Boddington

你也可以使用.collect(groupingBy(identity(), counting()))。 - Alexis C.

@AlexisC 我使用了LinkedHashMap来保持列表的顺序。 - Paul Boddington

Answer 8

像这样（使用Set）：

Something like this

Set<Object> blackList = new Set<>()

public void add(Object object) {
    if (blackList.exists(object)) {
        return;
    }
    boolean notExists = set.add(object);
    if (!notExists) {
       set.remove(object)
       blackList.add(object);
    }
}

- svarog

---

如果列表中有3个123，你该怎么办？ - Alexis C.

你会得到一个123的实例，这取决于你想要实现和做什么是好还是坏。从技术上讲，当你逐个插入值时，你逐个处理它们。因此，在第二次插入123之后，你需要将其删除。由于你的集合中没有123，所以重新插入它是可以的。 如果你想要更高级一些，可以使用黑名单。 - svarog

你将得到一个123的实例，这取决于你想要达到和做什么，是好是坏。但这不是OP想要做的。如果他在列表中有多个相同的字符串，他不希望它出现在最终的列表中。 - Alexis C.

你说得对，是我的错！我已经修改了代码。虽然还没有测试，但思路应该很明显。 - svarog

Answer 9

如果您想进行设置，则可以使用两个集合来实现。在另一个集合中保留重复的值，如下所示：

List<String> duplicateList = new ArrayList<String>();

duplicateList.add("123");
duplicateList.add("122");
duplicateList.add("125");
duplicateList.add("123");
duplicateList.add("127");
duplicateList.add("127");

System.out.println(duplicateList);

Set<String> nonDuplicateList = new TreeSet<String>();
Set<String> duplicateValues = new TreeSet<String>();

if(nonDuplicateList.size()<duplicateList.size()){
    for(String s: duplicateList){
        if(!nonDuplicateList.add(s)){
            duplicateValues.add(s);
        }
    }

    duplicateList.removeAll(duplicateValues);

    System.out.println(duplicateList);
    System.out.println(duplicateValues);
}

输出：原始列表：[123, 122, 125, 123, 127, 127]。删除重复项后：[122, 125]，重复的值为：[123, 127]。

注意：此解决方案可能不是最优解。您可能会找到比这更好的解决方案。

- Shadow Droid

Answer 10

我是Google Guava API的粉丝。使用Collections2工具和通用Predicate实现，可以创建一个实用方法以涵盖多种数据类型。

这假设所涉及的对象具有有意义的.equals实现。

@Test
    public void testTrimDupList() {
        Collection<String> dups = Lists.newArrayList("123", "122", "125", "123");
        dups = removeAll("123", dups);
        Assert.assertFalse(dups.contains("123"));

        Collection<Integer> dups2 = Lists.newArrayList(123, 122, 125,123);
        dups2 = removeAll(123, dups2);
        Assert.assertFalse(dups2.contains(123));
    }

    private <T> Collection<T> removeAll(final T element, Collection<T> collection) {
        return Collections2.filter(collection, new Predicate<T>(){
            @Override
            public boolean apply(T arg0) {
                return !element.equals(arg0);
            }});
    }

再深入思考一下

本页中的大多数其他示例都使用java.util.List API作为基础集合。我不确定是否出于意图，但如果返回的元素必须是List，则可以使用如下指定的另一个中间方法。多态万岁！

@Test
    public void testTrimDupListAsCollection() {
        Collection<String> dups = Lists.newArrayList("123", "122", "125", "123");
        //List used here only to get access to the .contains method for validating behavior.
        dups = Lists.newArrayList(removeAll("123", dups)); 
        Assert.assertFalse(dups.contains("123"));

        Collection<Integer> dups2 = Lists.newArrayList(123, 122, 125,123);
      //List used here only to get access to the .contains method for validating behavior.
        dups2 = Lists.newArrayList(removeAll(123, dups2));
        Assert.assertFalse(dups2.contains(123));
    }

    @Test
    public void testTrimDupListAsList() {
        List<String> dups = Lists.newArrayList("123", "122", "125", "123");
        dups = removeAll("123", dups);
        Assert.assertFalse(dups.contains("123"));

        List<Integer> dups2 = Lists.newArrayList(123, 122, 125,123);
        dups2 = removeAll(123, dups2);
        Assert.assertFalse(dups2.contains(123));
    }

    private <T> List<T> removeAll(final T element, List<T> collection) {
        return Lists.newArrayList(removeAll(element, (Collection<T>) collection));

    }
    private <T> Collection<T> removeAll(final T element, Collection<T> collection) {
        return Collections2.filter(collection, new Predicate<T>(){
            @Override
            public boolean apply(T arg0) {
                return !element.equals(arg0);
            }});
    }

- Jeremiah