The Algorithm Design Manual Problem 4-5

The mode of a set of numbers is the number that occurs most frequently in the
set. The set (4, 6, 2, 4, 3, 1) has a mode of 4. Give an efficient and correct algorithm
to compute the mode of a set of n numbers.

package avdongre.tadm;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class ModeOfSet {

	public int solveModeOfSetUsingHashMap(int[] input) {
		if ( input == null) {
			return -1;
		}
		if ( input.length <= 0 ) {
			return -1;
		}
		Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
		for (int i = 0; i < input.length; i++) {
			if (frequencyMap.containsKey(input[i])) {
				frequencyMap.put(input[i], frequencyMap.get(input[i]) + 1);
			} else {
				frequencyMap.put(input[i], 1);
			}
		}

		int maxFrequent = frequencyMap.get(input[0]);
		int currentFrequency = Integer.MIN_VALUE;

		for (Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
			Integer Key = entry.getKey();
			Integer Val = entry.getValue();

			if (currentFrequency < Val) {
				currentFrequency = Val;
				maxFrequent = Key;
			}

		}

		return maxFrequent;
	}

	public static void main(String[] args) {
		ModeOfSet mos = new ModeOfSet();
		{
			int[] input = new int[] { 4, 6, 2, 4, 3, 1 };
			System.out.println(mos.solveModeOfSetUsingHashMap(input));
		}
		{
			int[] input = new int[] { 4, 6, 2, 4, 3, 1, 1, 1, 1, 1 };
			System.out.println(mos.solveModeOfSetUsingHashMap(input));
		}
		{
			int[] input = new int[] {};
			System.out.println(mos.solveModeOfSetUsingHashMap(input));
		}		

	}

}


Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s