Faster/Easier method of finding number of duplicates of values in an array

Question

I am currently using a HashMap to correspond the duplicate values and the number of times they are repeated. Its linear efficiency O(n) but I was looking for some built-in methods or a faster way to calculate the number of duplicates for each value in an array (like O(log n))?.

Here is my current shot that works:

String[] array = {"Henry", "Henry", "Henry", "Maxwell", "Maxwell"};

HashMap<String, Integer> duplicates = new HashMap<String, Integer>();
int numberOfDuplicates = 1;

for (int i = 0; i < array.length; i++)
{
    if (duplicates.put(array[i], numberOfDuplicates) != null) // Duplicate Key
    {
        numberOfDuplicates++;
    }
    else // New Key
    {
        numberOfDuplicates = 1;
    }

    duplicates.put(array[i], numberOfDuplicates);
}


// Print out duplicate counts
for (String key : duplicates.keySet()) {
    System.out.println(key + " " + duplicates.get(key));
}

What about a faster way/pragmatic way? 10Q.

If it ain't broke, don't fix it. If you've got it to O(n) there's no reason to try to improve it, and the standard SDK doesn't have a method for this. Your code could look better though. — Kayaman
– Kayaman, Commented Jul 3, 2015 at 5:32
You could always use a multiset, such as from Guava, but it's basically doing this same thing. — chrylis -cautiouslyoptimistic-
– chrylis -cautiouslyoptimistic-, Commented Jul 3, 2015 at 5:35

Eran · Accepted Answer · 2015-07-03 05:43:49Z

1

You can write it with less code using Java 8 Streams :

Map<String, Integer> duplicates =
    Arrays.stream(array)
          .collect(Collectors.groupingBy(e -> e, 
                                         Collectors.reducing(0, e -> 1, Integer::sum);

answered Jul 3, 2015 at 5:43

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Kayaman · Accepted Answer · 2015-07-03 05:36:10Z

1

Here's a shot at removing some of the clutter.

String[] array = {"Henry", "Henry", "Henry", "Maxwell", "Maxwell"};

HashMap<String, Integer> duplicates = new HashMap<String, Integer>();

for (String s : array) {
    Integer i = duplicates.get(s);
    duplicates.put(s, i == null ? 1 : (i+1));
}

answered Jul 3, 2015 at 5:36

Kayaman

73.8k6 gold badges91 silver badges128 bronze badges

Comments

Ninad Pingale · Accepted Answer · 2015-07-03 05:40:57Z

1

You also can do it in following way

        if(duplicates.containsKey(array[i])){
            duplicates.put(array[i],duplicates.get(array[i])+1);
        }else{
            duplicates.put(array[i], 1);
        }

instead of

if (duplicates.put(array[i], numberOfDuplicates) != null) // Duplicate Key
    {
        numberOfDuplicates++;
    }
    else // New Key
    {
        numberOfDuplicates = 1;
    }

answered Jul 3, 2015 at 5:40

Ninad Pingale

7,0995 gold badges36 silver badges58 bronze badges

Comments

Michael Anderson · Accepted Answer · 2015-07-03 05:59:54Z

Trove Version

This is a modification of Kayamans answer using Trove, which is a high-performance collection library.

String[] array = {"Henry", "Henry", "Henry", "Maxwell", "Maxwell"};

TObjectIntMap<String> duplicates = new TObjectIntHashMap<String>();
for(String s: array) {
   duplicates.adjustOrPutValue(s,1,1);
}

duplicates.forEachEntry( new TObjectIntProcedure<String>() {
   void execute(String key, int value) {
      System.out.println(key + " " + value);
   };  
});

In place sort version

This version uses Arrays.sort and then steps through the array reporting duplicates. While Arrays.sort is O(n log n) the resulting algorithm may be faster due to it avoiding any allocations of data-structures - but it does change the order of the input array.

NOTE 1: In this case the timing will be dominated by the IO calls, so you may not notice the speed.

NOTE 2: I'd refactor and extract the core of this and use a functor to handle the processing of the duplicates.

Arrays.sort(array);
String last = null;
int count = 0;
for(String v:array) {

    // Is it the first value
    if(last = null) {
       last = v;
       count = 1;
       continue;
    }

    // Have we started a new value?
    if(last.equals(v)) {
       System.out.println(last + " " +count);
       last = v;
       count = 1;
       continue;
    }

    // Its a repeated value.
    ++count;
}

if(last!=null)
   System.out.println(last + " " +count);

Collectives™ on Stack Overflow

Faster/Easier method of finding number of duplicates of values in an array

4 Answers 4

Comments

Comments

Comments

Trove Version

In place sort version

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Trove Version

In place sort version

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related