C++, determine the mode of an array(urgent)

How do I determine the mode of an array?

additional information: Mode is a set of value which occurs most often.

Update:

i thought of sorting an array and compare each one, but i'm look for a more effective algorithm and what if there is more than one number that's the mode?

2 Answers

Rating
  • 1 decade ago
    Favorite Answer

    The most efficient way is to use Hashtable.

    The way you can go through all elements in the array at most ONCE.

    You can view Hashtable as another kind of array where it is great for locating value with a key.

    HT[key1] = value1;

    HT[key2] = value2;

    etc...

    Back to your question, suppose we have a hashtable for the element in the array, and the value of the element is the occurrences of such element in the array.

    So in the end, your hashtable looks like this:

    HT[element1] = 10

    HT[element2] = 5

    HT[element3] = 1

    HT[element4] = 30

    HT[element5] = 21

    ...

    MAX ELEMENT = element5

    MAX OCCURRENCE = 30

    Psuedo-code:

    Introduce a variable to keep track of the MAX ELEMENT with the MAX OCCURRENCE

    For each element in the array, do

    if (ELEMENT exists in the Hashtable)

    increment the OCCURRENCE for the element;

    if MAX OCCURRENCE < OCCURRENCE

    set MAX OCCURRENCE = OCCURRENCE and MAX ELEMENT to the ELEMENT

    else (insert the ELEMENT into the array with count of 1)

    So by going through the array ONCE you have the ELEMENT with the max "mode".

    This is a popular interview question in CS.

    Hashtable is good for lookups with the given key very efficiently.

    Many languages have that built-in (e.g. PERL, C++ - called map/hash-map).

    2007-03-05 07:30:29 補充:

    Sorting will work less efficiently.You have to 1) sort, 2) revisit the sorted array and do a countn = array size1) Fastest sort available is n*log(n)2) revisit takes nEfficiency = (n + 1)log(n), it is worse than n (as if you're using HT)Hope it helps!

    • Commenter avatarLogin to reply the answers
  • ?
    Lv 5
    1 decade ago

    I think if you can sort the array, then you can count each elements easily and find out the mode. (just by scanning through the array)

    Now the problem reduces to sorting an array. To sort the array, you can use bubble sort, or the sort() function defined in STL library.

    • Commenter avatarLogin to reply the answers
Still have questions? Get your answers by asking now.