Given an array of numbers, how do we find the element which appears most number of times? In statistics this element is called mode.
A simple solution is to count the frequency of all the elements in the array and select the one with maximum frequency. The outer loop selects an element, and the inner loop counts the frequency of the element. Obviously this solution takes O(n2) time.
A simple solution is to count the frequency of all the elements in the array and select the one with maximum frequency. The outer loop selects an element, and the inner loop counts the frequency of the element. Obviously this solution takes O(n2) time.
public static int mode( int[] array )
{
int maxCount = 1;
int maxElement = array[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( maxCount < count )
{
maxCount = count;
maxElement = array[i];
}
}
return maxElement;
}
Second Method:
In this method we sort the array first. Then all the equal elements will be placed together. We can count the frequencies easily.
public static int mode( int[] array )
{
Arrays.sort(array);
//Assume first element as the mode
int count = 1;
int maxCount = 1;
int maxElement = array[0];
//start from the second element
for( int i = 1; i < array.length; i++ )
{
//array[i] is same as previous element; increment count
if( array[i-1] == array[i] )
{
count++;
}
else //new element; update the maxCount, maxElement and reset count
{
if( maxCount < count )
{
maxCount = count;
maxElement = array[i-1];
}
count = 1;
}
}
return maxElement;
}
This method takes O( n log n ) time because sorting is involved. It runs O(1) space because constant extra space is required.
Third Method:
This method is based on map. We first calculate the frequencies of all the elements in the array and store them in a map.
Then we iterate through the map to find the maximum occurring element.
public static int mode( int[] array )
{
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
int i;
//Calculate the frequency map
for( i = 0; i < array.length; i++ )
{
//No entry in the map; add new with count 1
if( map.get(array[i]) == null )
{
map.put( array[i], 1 );
}
else //increment the count if already exists in the map
{
int valCount = map.get(array[i]);
map.put( array[i], ++valCount );
}
}
//iterate through the map to find the maximum occurring element
Iterator iter = map.keySet().iterator();
int maxFreq = 0;
int maxElement = 0;
while( iter.hasNext() )
{
Integer key = (Integer)iter.next();
int value = map.get(key);
if( value > maxFreq )
{< br /> maxFreq = value;
maxElement = key;
}
}
return maxElement;
}
This method runs in O(n) time but takes O(n) space for the map.