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.
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?
- 1 decade agoFavorite 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;
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
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!
- ?Lv 51 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.