How to find multiples of the same integer in an arraylist?

Question

Hi

My problem is as follows. I have an arraylist of integers. The arraylist contains 5 ints e.g[5,5,3,3,9] or perhaps [2,2,2,2,7]. Many of the arraylists have duplicate values and i'm unsure how to count how many of each of the values exist.

The problem is how to find the duplicate values in the arraylist and count how many of that particular duplicate there are. In the first example [5,5,3,3,9] there are 2 5's and 2 3's. The second example of [2,2,2,2,7] would be only 4 2's. The resulting information i wish to find is if there are any duplicates how many of them there are and what specific integer has been duplicated.

I'm not too sure how to do this in java.

Any help would be much appreciated. Thanks.

Answer 1

Two algorithms spring to mind.

Sort it (Collections.sort). Then iterate through easily finding dupes.

Iterate through keeping count in a Map<Integer,Integer> (or Map<Integer,AtomicInteger> for a mutable count). A bit ugly this way.

Either way, coding it should be an instructive exercise. I suggest doing both, and comparing.

Answer 2

Use a Hashmap collection in addition to the array list where

• the Hashmap key is the unique array int value and
• the Hashmap value to the key is the count of each value encountered.

Walk your array list collecting these values into the hashmap adding a new item when a previous key does not exist and incrementing by 1 the values of keys that do already exist. Then iterate over the Hashmap and print out any keys where the value is > 1.

Answer 3

You can go through the List and put them in a Map with the count. Then it is easy figure out which one is duplicated.

Answer 4

For a cleaner abstraction of what you're doing, you could use the Multiset data structure from guava/google-collections. You may even find you'd rather use it than a List, depending on what you're doing with it (if you don't need the deterministic ordering of a list). You'd use it like this:

Multiset<Integer> multiset = HashMultiset.create(list);
int count = multiset.count(3); // gets the number of 3s that were in the list

In terms of what the above is doing under the covers, it's almost exactly equivalent to the suggestion of building a Map<Integer,AtomicInteger> based on your list.

Answer 5

Here is a concrete implementation, with test, of what I described in comments to @Tom's answer:

package playground.tests;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

import junit.framework.TestCase;

public class DupeCounterTest extends TestCase {

    public void testCountDupes() throws Exception {
        int[] array = new int[] { 5, 5, 3, 3, 9 };
        assertEquals("{3=2, 5=2}", countDupes(array).toString());
    }

    private Map<Integer, AtomicInteger> countDupes(int[] array) {
        Map<Integer, AtomicInteger> map = new HashMap<Integer, AtomicInteger>();
        // first create an entry in the map for every value in the array
        for (int i : array)
            map.put(i, new AtomicInteger());
        // now count all occurrences
        for (int i : array)
            map.get(i).addAndGet(1);
        // now get rid of those where no duplicate exists
        HashSet<Integer> discards = new HashSet<Integer>();
        for (Integer i : map.keySet())
            if (map.get(i).get() == 1)
                discards.add(i);
        for (Integer i : discards) 
            map.remove(i);
        return map;
    }

}

Answer 6

To me, the most straightforward answer would be using the Collections.frequency method. Something along the lines of this:

ArrayList<Integer> intList // your list

Set<Integer> noDupes = new HashSet<Integer>;
noDupes.addAll(intList); // all duplicates removed.

for (Integer i : noDupes) {

 int occurrences = Collections.frequency(intList, i);
 System.out.println(i + " occurs " + occurences + " times.");
}

If you want to, you could map each integer with its number of occurrences:

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Integer i : noDupes) {
 map.put(i, Collections.frequency(intList, i)
}