Find the element with highest occurrences in an array [java]

Question

I have to find the element with highest occurrences in a double array. I did it like this:

int max = 0;
for (int i = 0; i < array.length; i++) {
       int count = 0;
       for (int j = 0; j < array.length; j++) {
         if (array[i]==array[j])
             count++;
   }
  if (count >= max)
      max = count;
 }

The program works, but it is too slow! I have to find a better solution, can anyone help me?

Answer 1

Update:

• As Maxim pointed out, using HashMap would be a more appropriate choice than Hashtable here.
• The assumption here is that you are not concerned with concurrency. If synchronized access is needed, use ConcurrentHashMap instead.

---

You can use a HashMap to count the occurrences of each unique element in your double array, and that would:

• Run in linear O(n) time, and
• Require O(n) space

Psuedo code would be something like this:

• Iterate through all of the elements of your array once: O(n)
  • For each element visited, check to see if its key already exists in the HashMap: O(1), amortized
  • If it does not (first time seeing this element), then add it to your HashMap as [key: this element, value: 1]. O(1)
  • If it does exist, then increment the value corresponding to the key by 1. O(1), amortized
• Having finished building your HashMap, iterate through the map and find the key with the highest associated value - and that's the element with the highest occurrence. O(n)

A partial code solution to give you an idea how to use HashMap:

import java.util.HashMap;
...

    HashMap hm = new HashMap();
    for (int i = 0; i < array.length; i++) {
        Double key = new Double(array[i]);
        if ( hm.containsKey(key) ) {
            value = hm.get(key);
            hm.put(key, value + 1);
        } else {
            hm.put(key, 1);
        }
    }

I'll leave as an exercise for how to iterate through the HashMap afterwards to find the key with the highest value; but if you get stuck, just add another comment and I'll get you more hints =)