How do you detect and delete more than two duplicates in an Array?

Question

How do you detect and delete if there more than two duplicates in an array. In the following example, I have taken an array with the elements "10, 20, 30, 40, 40, 40, 50, 60, 70, 80 ,10". Here 40 is repeated thrice and 10 is repeated twice. I could write a program to detect two duplicates but I am not able to shrink 40(repeated thrice) to once. Note:- I want to do this without using any java collection

public class ArrayDuplicate {
public void run1()
{
    int[] a = {10, 20, 30, 40, 40, 40, 50, 60, 70, 80 ,10};
    int size=a.length;
    System.out.println("Array size before duplicate deletion "+size);
    for(int i =0;i<(size-1);i++)
    {
        for(int j=i+1;j<=(size-1);j++)
        {
            if(a[i]==a[j] &&i!=j)
            { 
                while(j<(size-1))
                {
                a[j]=a[j+1];
                j++;

                }
                size--;
            }

        }
    }
    System.out.print("The array after deleting the duplicates is ");
    for(int k=0;k<=(size-1);k++)
    {
        System.out.print(a[k]);  //40 is being printed twice
        if(k<(size-1))
        {
            System.out.print(",");
        }
        else
            System.out.print(".");
    }




}
public static void main(String[] args)
{
    ArrayDuplicate ob = new ArrayDuplicate();
    ob.run1();

}

}

https://stackoverflow.com/questions/17967114/how-to-efficiently-remove-duplicates-from-an-array-without-using-set — assylias, Aug 03 '17 at 11:51
What exact output do you expect? If you just want each element once, you could add the list to a set. — Tim Biegeleisen, Aug 03 '17 at 11:52
The output is 10,20,30,40,40,50,60,70,80. The 40 is getting repeated twice. I want the output to be 10,20,30,40,50,60,70,80 — Gaurav Thantry, Aug 03 '17 at 11:56
@GauravThantry if you don't want array order then you can sort the array and then try your code. To sort array in asc order try this tutorial i randomly searched for http://www.sanfoundry.com/java-program-sort-array-ascending-order/ — Raju Sharma, Aug 03 '17 at 11:59
Just as a note: Here at SO we have so many questions about *"how to remove duplicates"*. I am sure that a quick research will help you solve the problem: [Quick search](https://www.google.de/search?q=stackoverflow+java+remove+duplicates+array&oq=stackoverflow+java+remove+duplicates+array). You can also use those `Set` techniques to reduce duplicates only to a specific amount. Therefore just use a `Map` where the keys are your elements and the values are counters that count how often you have seen the duplicate already. — Zabuzard, Aug 03 '17 at 12:04
If you want each element of your Array to be unique, use a Set (https://docs.oracle.com/javase/7/docs/api/java/util/Set.html). This also allows you to sort the elements in ascending order. — Asew, Aug 03 '17 at 12:06
Problem in your code is that for first 40 (from outer loop), your inner loop finds 2nd 40 and adjusts the elements of the array, but when you find 3rd 40 , your inner loop starts searching for 40 from the position after the position of 3rd 40 and you don't find any other element = 40, so there are 2 40s. — deepakl, Aug 03 '17 at 12:09
i added an Edit2 on my answer with a solution without any java collection — albert_nil, Aug 03 '17 at 12:34
@GauravThantry, try my answer it just need 4 characters to add in your code . by rechecking adjacent for duplicate — Raju Sharma, Aug 03 '17 at 12:54

albert_nil · Answer 1 · 2017-08-03T12:33:43.307

3

You said that you only wanted to keep one element for those that are present 3 times or more in the list (not 2). If they were 2 or more, a TreeSet would be the only thing you would need.

You said that after being present 3 or more times, you only wanted to keep 1.

Here you are:

int[] input = whatever_your_input;

List<Integer> result = new ArrayList<>();
Map<Integer, Integer> valueCounter = new HashMap<>();

for (int i=0; i<input.length; i++) {
    int counter = valueCounter.get(input[i]);
    if (counter = null) {
        counter = 0;
    } 
    valueCounter.put(input[i], counter++);
    if (counter <3) {
        result.add(input[i]);
    }
 }

result will contain the output list.

Edit: Just to be clear, if you don't want any duplicate at all you only need this:

int[] input = whatever_your_input;

Set<Integer> result = new TreeSet<>();
for (int i=0; i<input.length; i++) {
     result.add(input[i]);
}

result will then contain your original list without any duplicate, and while keeping same sorting.

Edit2: Ok, it seems what OP wants is no duplicate at all. Also, no java Collection to be used. Here we go:

int[] input = whatever_your_input;

int[] tmpResult = new int[input.length];
int tmpLength = 0;

for (int i=0; i<input.length; i++) {
    boolean duplicated = false;
    for (int j=0; j<tmpLength; j++) {
        if (tmpResult[j] == input[i]) {
             duplicated = true;
             break;
        }
     }
     if (!duplicated) {
         tmpResult[tmpLength] = input[i];
         tmpLength++;
     }
}
int[] result = new int[tmpLength];
System.arraycopy(tmpResult, 0, result, 0, tmpLength);

result will contain values in same order and withot duplicates.

edited Aug 03 '17 at 12:33

answered Aug 03 '17 at 12:05

albert_nil

1,648
7
9

I am unsure if that really is what OP wants. For me the question sounds like "*I am able to remove duplicate values if there are 2 of them but not if greater, how to do that?*". But in any case your answer is *useful* in my opinion. – Zabuzard Aug 03 '17 at 12:10
appreciate your feedback @Zabuza but the OP wrote "How do you detect and delete if there more than two duplicates in an array". In any case, since i felt like he only wanted to ensure no duplicates at all, i started by saying that then a TreeSet was enough, nothing more. – albert_nil Aug 03 '17 at 12:12
@albert_nil Can't we get this by using only Arrays ? I could have used the 'List' class as it doesn't allow any duplicates, but I wanted to do this by using only arrays. – Gaurav Thantry Aug 03 '17 at 12:16
for sure it can be done, but then please edit your question to reflect you wanted avoid the use of any java Collection – albert_nil Aug 03 '17 at 12:17
btw, List allow duplicates, it's Set the one that avoids that – albert_nil Aug 03 '17 at 12:18
The problem with arrays is that they do not efficiently can answer something like `contains(element)`, but Sets like `HashSet` for example do. So if you just use arrays you need to, for every element, check the whole array for duplicates. And that approach works in `O(n^2)` time complexity which quickly gets very bad for larger inputs (even if you optimize it a bit here and there). In contrast to that the `HashSet` approach works in `O(n)`. – Zabuzard Aug 03 '17 at 12:26

score 2 · Answer 2 · answered Aug 03 '17 at 12:09

2

int[] a = {10, 20, 30, 40, 40, 40, 50, 60, 70, 80 ,10};
Set<Integer> set = new HashSet<Integer>();
for (int i : a) {
   set.add(i);
}
a = set.toArray(new int[set.size()]);

Hope that help you!

answered Aug 03 '17 at 12:09

Yugerten

878
1
11
30

While this answer is indeed helpful I think you could improve the quality by explaining the approach. You could explain the advantages of `Set`s and why they help to solve the problem. – Zabuzard Aug 03 '17 at 12:11
this would remove the sorting (but not explicitely stated by OP that he wants sorting to be retained). – albert_nil Aug 03 '17 at 12:14
1

the idea is: the Java Set collection dont support duplication – Yugerten Aug 03 '17 at 12:15

score 1 · Answer 3 · answered Aug 03 '17 at 12:45

I think the OP doesnt want to use Collections to remove duplicates. So i just modified his code to look as below.

for (int i = 0; i < (size - 1); i++) {
                  for (int j = i + 1; j <= (size - 1); j++) {
                        if (a[i] == a[j] && i != j) {
                              while (j < (size - 1)) {
                                    a[j] = a[j + 1];
                                    j++;

                              }
                              i--;//recheck in inner for loop is performed (i--) , to check adjacent duplicate element.
                              size--;
                        }

                  }
            }

Here an recheck in inner for loop is performed (i--) , to check adjacent duplicate element.

score 1 · Answer 4 · answered Aug 03 '17 at 12:46

Hope below code will do.

public static void main(String[] args) {

    int[] a = { 10, 20, 30, 40, 40, 40, 50, 60, 70, 80, 10 };

    Map<Integer, Integer> m = new HashMap<Integer, Integer>();
    ArrayList<Integer> al = new ArrayList<Integer>();

    for (int i = 0; i < a.length; i++) {
        int count = 1;

        if (m.containsKey(a[i])) {

            m.put(a[i], m.get(a[i]) + 1);
        }

        else {
            m.put(a[i], count);
        }

    }

    for (int i = 0; i < a.length; i++) {

        if (m.get(a[i]) > 2) {

        } else {
            al.add(a[i]);
        }

    }
    System.out.println(al);

}

score 1 · Accepted Answer · edited Aug 03 '17 at 21:38

I know why the 40 is getting repeated twice.In your loop, when i = 3 and j = 4, a[i] = a[j],so in while-loop,the array moves left,
a[4] = a[5],a[5] = a[6],a[6] = a[7], a[7] = a[8]...
then,
a[] = {10, 20, 30, 40, 40, 50, 60, 70, 80 ,10} ,size = 9,j= 9.
continues the for-loop,i = 4,j =5,but when i = 3, a[3] = a[4] = 40,so the loop can't shrink 40(repeated thrice) to once. I modified your code as shown below.

  public class ArrayDuplicate {
    public void run1()
    {
        int[] a = {10, 20, 30, 40, 40, 40, 50, 40, 60, 70, 80 ,10};
        int size=a.length;
        System.out.println("Array size before duplicate deletion "+size);
        for(int i =0;i<(size-1);i++)
        {
            for(int j=i+1;j<=(size-1);j++)
            {
                if(a[i]==a[j] &&i!=j)
                {      
                    int temp = j;
                    while(temp<(size-1))
                    {
                        a[temp]=a[temp+1];
                        temp++;
                    }
                    size--;
                    j=i;  
                }

            }
        }
        System.out.print("The array after deleting the duplicates is ");
        for(int k=0;k<=(size-1);k++)
        {
            System.out.print(a[k]);  //40 is being printed twice
            if(k<(size-1))
            {
                System.out.print(",");
            }
            else
                System.out.print(".");
        }
    }
    public static void main(String[] args)
    {
        ArrayDuplicate ob = new ArrayDuplicate();
        ob.run1();

    }
}

score 0 · Answer 6 · answered Aug 03 '17 at 12:33

Implementations of Set cannot hold duplicates, so by inserting all values into a Set all the deplicates would be removed.

Using Java 8 Streams and Collections this could be implemented like:

// Remove all duplicates by inserting into a Set
Set<Integer> noDupes = Arrays.stream(a).boxed().collect(Collectors.toCollection(TreeSet::new));

// Set to primitive array
a = noDupes.stream().mapToInt(Integer::intValue).toArray();

then a would hold the original values minus duplicates.

How do you detect and delete more than two duplicates in an Array?

6 Answers6