Find the Mode of an Array in Java

[courtrigrad]

How would i write a program in java such that if you input an array, it returns the mode of the array. IF there is more than one mode, return the first mode.
Here is my code so far:

any help is appreciated!

thanks

 

[gnome]

First sort the array.
Then think about it some more.

 

[Hurkyl]

Well, a mode is the element with the greatest frequency, right?

Do you know how to find frequency counts?


Sorting? Bah! I can do it in O(n) time!

 

[gnome]

Really? I didn't know there was any way better than O(nlogn) (using a comparison algorithm).

 

[Hurkyl]

Oh, I mean I can do the problem in O(n) time, I didn't mean I can sort in O(n) time (except in special cases).



PS, courtigrad, don't worry about efficiency. Worry about figuring out a way to do it first, then worry about doing it better if you have time / interest.

 

[courtrigrad]

// Program returns the mode of an array. If there is more than one mode
// it returns the first mode.
public class Mode
{
    public int Modes(int [] a)  // method for class
    {
        int i;
        int frequency [] = new int[ a.length + 1 ];
         
        for( i = 0; i < a.length; i++) 
            ++frequency[ a[i] ];
        
            
    }
        if( frequency[ a[i] ] > frequency[ a[i + 1] ]
        {
            return a[i];
        }
 }

is this right?

 

[gnome]

Do you know that a is an array of integers?

if so, suppose a is an array of 100 integers, the biggest one being 56,789.
What if the biggest one is 2,147,483,647?

Now what?

 

[courtrigrad]

i would have to sort it from leastest to greatest and then find the frequencies. Then check which one has highest frequency

 

[gnome]

Yes, that's what i was thinking. I don't know how Hurkyl's idea would apply in that kind of situation (i.e. very large integers, strings, or other kinds of non-integer data types).

Were you told what kind of data is in the array?

 

[courtrigrad]

yes, just integers


maybe i should start like this?

 // Program returns the mode of an array. If there is more than one mode
// it returns the first mode.
public class Mode
{
    public void sort()
    {
        int i;
        for( i = 1; i < a.length; i++)
            for( i = 0; i < a.length - 1; i++)
              if( a[i] > a[ i + 1] 
              {
                  hold = a[i];
                  a[i] = a[i+1];
                  a[i+1] = hold;
              }
    }

 

[gnome]

Well, sorting works for any kind of integers, so you know one way to do it. If you want to take it further and you have more information about what's in the array you may be able to come up with a way to do it without sorting. Suppose, for example, that you know that it's only small positive integers. Think about that (I'm not going to give it to you -- that would spoil it).

 

[The Idiot]

I have an idea of how to do it, without sorting, in n time, for any integers, be they small or large. It would take some more advanced things, though...

Edit: It might be worth it, though, since it's supposed to return the first mode if there are duplicates. I'm betting that this array is probably already sorted, though, if I know programming classes, and assuming that this one isn't very advanced.