Remove duplicates in an array without changing order of elements

Question

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

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

Answer 1

Bro this is you answer but this have 0(n2) T.C remember.

vector<int> sol(int arr[],int n){
vector<int> dummy;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
    if(arr[i]==arr[j]){
        dummy.push_back(j);
    }
   }
 }
 vector<int> ans;
 for(int i=0;i<n;i++){
 bool check=true;
  for(int j=0;j<dummy.size();j++){
    if(dummy[j]==i){
        check=false;
    }
 }
 if(check==false)
   continue;
  ans.push_back(arr[i]);
  }
  return ans;
  }

Answer 2

Without LinkedHashSet overhead (uses HashSet for seen elements instead which is slightly faster):

List<Integer> noDuplicates = list
        .stream()
        .distinct()
        .collect(Collectors.toList());

Note that the order is guaranteed by the Stream.distinct() contract:

For ordered streams, the selection of distinct elements is stable (for duplicated elements, the element appearing first in the encounter order is preserved.)

Answer 3

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

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

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

}
    }

Answer 4

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.

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

Answer 5

There are 2 ways:

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)

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 !!!

Answer 6

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

// list is some List of Strings

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

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

Answer 7

Use an instance of java.util.LinkedHashSet.

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

Answer 8

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

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.

Answer 9

With this one-liner:

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

Answer 10

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.

Answer 11

Use LinkedHashSet to remove duplicate and maintain order.

Answer 12

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

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

And convert it back to whatever you want.

Note: If you want to preserve order, use LinkedHashSet instead.