CODEWITHSUNDEEP
arrays
Rajendra Uppal
Rajendra Uppal

Reputation: 19914

Find maximum occuring integer (Mode) in an unsorted array

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?

Upvotes: 3

Views: 7904

Answers (5)

Pranaya Prakash
Pranaya Prakash

Reputation: 1

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");
}

}

Upvotes: 0

CoooolllYuvee
CoooolllYuvee

Reputation: 113

Here's a basic outline of what you will be doing:

  1. First sort the array - O(n logn) incase of a merge sort
  2. Declare Count=1, Max_Count=1, Max_Value=arr[0]
  3. Iterate through array starting at index 1
  4. Compare each element with Previous element. Update the count, Max_Count if they are equal, else reset count back to 1
  5. 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");
}

Upvotes: 4

sud03r
sud03r

Reputation: 19749

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.

Upvotes: 0

Axarydax
Axarydax

Reputation: 16603

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.

Upvotes: 3

Chris
Chris

Reputation: 27384

If you are using Linq you can do this

IEnumerable.Max();

Upvotes: 0

Related Questions