How to find the integer occurring maximum number of times (mode) in an unsorted array of integers?
One O(nlogn) approach I could think of is to sort. Is there any other better approach?
Add a comment
|
5 Answers
Here's a basic outline of what you will be doing:
- First sort the array - O(n logn) incase of a merge sort
- Declare Count=1, Max_Count=1, Max_Value=arr[0]
- Iterate through array starting at index 1
- Compare each element with Previous element. Update the count, Max_Count if they are equal, else reset count back to 1
- return Max_Count, Max_value
Time Complexity : O(n logn)+ O(n) Space Complexity : InPlace , no hash table or hash map is required.
Here is the code:
public void Max_Occurrence(int[] arr)
{
int count=1;
int max_count =1;
int max_value = arr[0];
for(int i=1; i<arr.length ; i++)
{
if(arr[i-1] == arr[i])
{
count++;
if(max_count<count)
{
max_count = count;
max_value = arr[i];
}
}
else
{
count = 1;//changing from count++. As per the steps mentioned above it should be reset to count = 1. Suggested by an anonymous user
}
}
System.out.println("Result:"+max_value+" has occured "+max_count+"of times");
}
Comments
I think you want to find out element that has most occurences in the array - if you don't care about memory, traverse the array once, increase count of each element in the hashtable. Then find the one with highest count. You'd need one traverse of array and one of the hashtable.
so in pseudocode:
hashtable hash;
foreach(element in array){
if(!hash.contains(element))
hash[element] = 1;
else
hash[element]++;
}
int max = 0;
max_element;
foreach(element in hash)
if(hash[element] > max)
{
max_element = element;
max = hash[element];
}
//max_element contains the maximum occuring one.
4 Comments
Rajendra Uppal
@Axerydax What if there are 10 million integers and ofcourse I don't want to use 10 million integer extra space?
sud03r
@Rajendra, you may then like to use a hash table which uses a hash function to create keys, and not uses the array index as key.
Rajendra Uppal
@Neeraj Fine, agreed. What is your take on a situation like following? 1. array of 10 million integers. 2. only one duplicate (our answer) 3. rest (10 million - 2) are distinct integers.
sud03r
@Rajendra,you can take an array of size 2*10 million, use a hash function and hash the entries, avoid collision by linear probing or separate chaining and proceed in way as described.Also if the range of numbers in your array is small,you can further extend the method demonstrated by Axarydax by using
(element - min) in place of elementIf you are using Linq you can do this
IEnumerable.Max();
1 Comment
Rajendra Uppal
My dear friends, I know this, please read my comment on Younes's answer. I can write myself one templated function that would find minimum and maximum integer from an array of int, float, or double, or long type.
You can use a hashtable with "the number in array" as key and "occurrences" as values.
Sample code be like this:
hashtable h;
for every entry in array
search hashtable
if present, increment num_occurrences
else, create new entry
Iterate over all the entries in hashtable and return one
with max num_occurrences
As searching in hash is considered O(1), the overall complexity will be O(n).
A special case of this problem is when the numbers in array are in a given range, in that case take another array of ints with size of maximum value in the original array,and use the index of new array as key and the number stored in this array as count of occurrences.
Return the index of the largest value in this array.
Comments
Try this.
class max_frequency
{
private int a[]=new int[20];
public void accept(int a1[])
{
a=a1;
}
public void sort()
{
int i,j,t;
for(i=0;i<20;i++)
{
for(j=i+1;j<20;j++)
{
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
int count=1;
int max_count=1;
int max_value=0;
for(i=1;i<a.length;i++)
{
if(a[i-1]==a[i])
{
count++;
if(max_count<count)
{
max_count=count;
max_value=a[i];
}
}
else
{
count=1;
}
}
System.out.println("Result : "+max_value+ " has occured "+max_count+ " times");
}
}
