Java 在不改变元素顺序的情况下删除数组中的重复项

Remove duplicates in an array without changing order of elements

提问by Deqing

I have an array, say List<Integer>139, 127, 127, 139, 130

我有一个数组，说 List<Integer>139, 127, 127, 139, 130

How to remove duplicates of it and keep its order unchanged? i.e. 139, 127, 130

如何删除它的重复项并保持其顺序不变？IE139, 127, 130

采纳答案by Paul Vargas

Use an instance of java.util.LinkedHashSet.

使用java.util.LinkedHashSet.

Set<Integer> set = new LinkedHashSet<>(list);

回答by Maroun

Construct Setfrom your list - "A collection that contains no duplicate elements":

Set从您的列表构建- “一个不包含重复元素的集合”：

Set<Integer> yourSet = new HashSet<Integer>(yourList);

And convert it back to whatever you want.

并将其转换回您想要的任何内容。

Note: If you want to preserve order, use LinkedHashSetinstead.

注意：如果要保留顺序，请LinkedHashSet改用。

回答by Masudul

Use LinkedHashSetto remove duplicate and maintain order.

使用LinkedHashSet去除重复和维持秩序。

回答by Antoniossss

As I cant deduct, you need to preserve insertion order, that compleating what @Maroun Maroun wrote, use set, but specialidez implementation like LinkedHashSet<E>whitch does exactly the thing you need.

正如我无法推断的那样，您需要保留插入顺序，即完成@Maroun Maroun 所写的内容，使用 set，但是像LinkedHashSet<E>whiitch 这样的specialidez 实现正是您所需要的。

回答by Andrey Chaschev

With this one-liner:

有了这个单线：

yourList = new ArrayList<Integer>(new LinkedHashSet<Integer>(yourList))

回答by constpetrov

Iterate through array (via iterator, not foreach) and remove duplicates. Use set for find duplicates.

遍历数组（通过迭代器，而不是 foreach）并删除重复项。使用 set 查找重复项。

OR

或者

Iterate through array and add all elements to LinkedHashSet, it isn't allows duplicates and keeps order of elements. Then clear array, iterate through set and add each element to array.

遍历数组并将所有元素添加到 LinkedHashSet，它不允许重复并保持元素的顺序。然后清除数组，遍历 set 并将每个元素添加到数组中。

回答by Sampath Kumar

Although converting the ArrayList to a HashSet effectively removes duplicates, if you need to preserve insertion order, I'd rather suggest you to use this variant

尽管将 ArrayList 转换为 HashSet 可以有效地删除重复项，但如果您需要保留插入顺序，我还是建议您使用此变体

// list is some List of Strings

// list 是一些字符串列表

   Set<String> s = new LinkedHashSet<String>(list);

Then, if you need to get back a List reference, you can use again the conversion constructor.

然后，如果您需要取回 List 引用，您可以再次使用转换构造函数。

回答by Spektre

There are 2 ways:

有2种方式：

1. create new list with unique ints only

   • (the same as Maroun Maroun answer)

   • you can do it with 2 nested fors like this O(n.n/2):

     List<int> src,dst;
     // src is input list
     // dst is output list
     dst.allocate(src.num); // prepare size to avoid slowdowns by reallocations
     dst.num=0;             // start from empty list
     for (int i=0;i<src.num;i++)
      {
      int e=1;
      for (int j=0;i<dst.num;i++)
       if (src[i]==dst[j]) { e=0; break; }
      if (e) dst.add(src[i]);
      }
     

2. You can select duplicate items and delete them ... O(2.n) with the flagged delete

   • this is way much faster but you need memory table for whole int range
   • if you use numbers <0,10000> then it will take BYTE cnt[10001]
   • if you use numbers <-10000,10000> then it will take BYTE cnt[20002]
   • for small ranges like this is ok but if you have to use 32 bit range it will take 4GB !!!
   • with bit packing you can have 2 bits per value so it will be just 1GB but that is still too much for my taste

   • ok now how to check for duplicity ...

     List<WORD> src;  // src is input list
     BYTE cnt[65536]; // count usage for all used numbers
     int i;
     for (i=0;i<65536;i++) cnt[i]=0; // clear the count for all numbers
     for (i=0;i<src.num;i++)         // compute the count for used numbers in the list  
      if (cnt[src[i]]!=255) 
       cnt[src[i]]++;
     

   • after this any number i is duplicate if (cnt[i]>1)
   • so now we want to delete duplicate items (all except one)

   • to do that change cnt[] like this

     for (i=0;i<65536;i++) if (cnt[i]>1) cnt[i]=1; else cnt[i]=0;
     

   • ok now comes the delete part:

     for (i=0;i<src.num;i++)         
      if (cnt[src[i]]==1) cnt[src[i]]=2; // do not delete the first time
       else if (cnt[src[i]]==2)          // but all the others yes
        { 
        src.del(i);
        i--;                             // indexes in src changed after delete so recheck for the same index again
        }
     

3. you can combine both approaches together

4. delete item from list is slow because of item shift in the list
   • but can be speed up by adding delete flag to items
   • instead of delete just set the flag
   • and after all items to delete is flagged then simply remove hem at once O(n)

1. 创建仅具有唯一整数的新列表

   • （与Maroun Maroun 回答相同）

   • 你可以用 2 个嵌套的 fors 来做，像这样 O(nn/2)：

     List<int> src,dst;
     // src is input list
     // dst is output list
     dst.allocate(src.num); // prepare size to avoid slowdowns by reallocations
     dst.num=0;             // start from empty list
     for (int i=0;i<src.num;i++)
      {
      int e=1;
      for (int j=0;i<dst.num;i++)
       if (src[i]==dst[j]) { e=0; break; }
      if (e) dst.add(src[i]);
      }
     

2. 您可以选择重复项并删除它们... O(2.n) 带有标记的删除

   • 这要快得多，但您需要整个 int 范围的内存表
   • 如果您使用数字 <0,10000> 那么它将占用 BYTE cnt[10001]
   • 如果您使用数字 <-10000,10000> 那么它将占用 BYTE cnt[20002]
   • 对于像这样的小范围是可以的，但是如果您必须使用 32 位范围，则需要 4GB ！！！
   • 使用位打包，每个值可以有 2 位，因此只有 1GB，但这对我来说仍然太多了

   • 好的，现在如何检查口误...

     List<WORD> src;  // src is input list
     BYTE cnt[65536]; // count usage for all used numbers
     int i;
     for (i=0;i<65536;i++) cnt[i]=0; // clear the count for all numbers
     for (i=0;i<src.num;i++)         // compute the count for used numbers in the list  
      if (cnt[src[i]]!=255) 
       cnt[src[i]]++;
     

   • 在此之后，如果 (cnt[i]>1)，任何数字 i 都是重复的
   • 所以现在我们要删除重复的项目（除了一个）

   • 像这样改变 cnt[]

     for (i=0;i<65536;i++) if (cnt[i]>1) cnt[i]=1; else cnt[i]=0;
     

   • 好的，现在是删除部分：

     for (i=0;i<src.num;i++)         
      if (cnt[src[i]]==1) cnt[src[i]]=2; // do not delete the first time
       else if (cnt[src[i]]==2)          // but all the others yes
        { 
        src.del(i);
        i--;                             // indexes in src changed after delete so recheck for the same index again
        }
     

3. 您可以将这两种方法结合在一起

4. 由于列表中的项目移动，从列表中删除项目很慢
   • 但可以通过向项目添加删除标志来加快速度
   • 而不是删除只是设置标志
   • 在标记了所有要删除的项目之后，只需立即删除下摆 O(n)

PS. Sorry for non standard list usage but i think the code is understandable enough if not comment me and i respond

附注。抱歉非标准列表使用，但我认为代码是可以理解的，如果不评论我，我会回应

PPS. for use with signed values do not forget to shift the address by half range !!!

聚苯乙烯。对于有符号值，不要忘记将地址移动一半范围！！！

回答by Dharmendra Pratap Singh

Below I have given the sample example that implements a generic function to remove duplicate from arraylist and maintain the order at the same time.

下面我给出了示例示例，该示例实现了一个通用函数，以从 arraylist 中删除重复项并同时保持顺序。

import java.util.*;
public class Main {
    //Generic function to remove duplicates in list and maintain order
    private static <E> List<E> removeDuplicate(List<E> list) {
        Set<E> array = new LinkedHashSet<E>();
        array.addAll(list);
        return new ArrayList<>(array);
    }
    public static void main(String[] args) {
        //Print [2, 3, 5, 4]
        System.out.println(removeDuplicate(Arrays.asList(2,2,3,5, 3, 4)));
        //Print [AB, BC, CD]
        System.out.println(removeDuplicate(Arrays.asList("AB","BC","CD","AB")));
    }
}

回答by Soudipta Dutta

Method 1 : In Python => Using a set and list comprehension

方法 1：在 Python 中 => 使用集合和列表推导式

a= [139, 127, 127, 139, 130]

print(a)
seen =set()
aa = [ch  for ch in a if ch not in seen and not seen.add(ch)]
print(aa)

Method 2 :

方法二：

aa = list(set(a))
print(aa)

In Java : using Set and making a new ArrayList

在 Java 中：使用 Set 并创建一个新的 ArrayList

class t1 {
    public static void main(String[] args) {

int[] a = {139, 127, 127, 139, 130};
List<Integer> list1 = new ArrayList<>();

Set<Integer> set = new LinkedHashSet<Integer>();
for( int ch  : a) {
    if(!set.contains(ch)) {
        set.add(ch);
    }


}//for
set.forEach( (k) -> list1.add(k));
System.out.println(list1);

}
    }