Detect duplicate values in primitive Java array

Question

I want to detect duplicate values in a Java array. For example:

int[] array = { 3, 3, 3, 1, 5, 8, 11, 4, 5 };

How could I get the specific duplicated entry and how many times it occurs?

Solution 1

I'll have a Map<Integer, Integer> where the first integer is the value of the number that occurs in the array and the second integer is the count (number of occurrence).

• Run through the array.length in a loop
• for each item in the array, do a map.containsKey(array[i]). If there exists a number in a map, increment that number (something like map.put(array[i], map.get(array[i]) + 1). Otherwise, create a new entry in a map (e.g map.put(array[i], 1).
• Finally, iterate through the map and retrieve all keys where value is greater than 1.

Solution 2

Seems like a job for data structure called multiset.

Multiset<Integer> mp = HashMultiset.create();
mp.addAll(Arrays.asList(new Integer[] { 3, 3, 3, 1, 5, 8, 11, 4, 5 }));

Standard JDK 6 is primitive and do not contain multiset. If you do not want to rewrite it, you can use preexisting library like Google Guava-libraries or Apache Commons.

For example with Guava-libraries you can

    for (Integer i : mp.elementSet())
        System.out.println(i + " is contained " + mp.count(i) + " times.");

And this would output:

1 is contained 1 times.
3 is contained 3 times.
4 is contained 1 times.
5 is contained 2 times.
8 is contained 1 times.
11 is contained 1 times.

Solution 3

The answer depends on the number range in your source array. If the range is small enough you can allocate an array, loop through your source and increment at the index of your source number:

int[] counts = new int[max_value + 1];

for (int n: array) {
    counts[n]++;
}

If your source array contains an unknown or too large range, you can create a Map and count in that:

Map<Integer,Integer> counts = new HashMap<Integer,Integer>();

for (Integer n: array) {
    if (counts.containsKey(n)) {
        counts.put(n, counts.get(n) + 1);
    } else {
        counts.put(n, 1);
    }
}

NB. typed the above without the help of a JVM, getting rid of typoes is left as an exercise for the reader :-)

Solution 4

public class Duplicate {

    public static void main(String[] arg) {
        int[] array = {1, 3, 5, 6, 2, 3, 6, 4, 3, 2, 1, 6, 3};

        displayDuplicate(array);

    }

    static void displayDuplicate(int[] ar) {
        boolean[] done = new boolean[ar.length];
        for(int i = 0; i < ar.length; i++) {
            if(done[i])
                continue;
            int nb = 0;
            for(int j = i; j < ar.length; j++) {
                if(done[j])
                    continue;
                if(ar[j] == ar[i]) {
                    done[j] = true;
                    nb++;
                }
            }
            System.out.println(ar[i] + " occurs " + nb + " times");
        }
    }
}

Solution 5

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class DuplicatedValuesInArray 
{

    public static void main(String args[]) {  
        int[] array = { 3, 3, 3, 1, 5, 8, 11, 4, 5 };
        Map<Integer, Integer> map= new HashMap<Integer, Integer>();

      for(int i=0;i<array.length;i++) {   
          if(map.containsKey(array[i]))

          map.put(array[i],map.get(array[i]) + 1);
      else
          map.put(array[i], 1);
      }

      for (Integer i : map.keySet()) {
          System.out.println(i + " is contained " + map.get(i) + " times.");
      }
   }
}

View more solutions