Search code examples
algorithmstatisticsselectionmode

Computing the statistical mode

I'm currently trying to verify whether or not, given an unsorted array A of length N and an integer k, whether there exists some element that occurs n/k times or more.

My thinking for this problem was to compute the mode and then compare this to n/k. However, I don't know how to compute this mode quickly. My final result needs to be nlog(k), but I have no idea really on how to do this. The quickest I could find was nk...

Solution

  • Use a hash table to count the frequency of each value:

    uint[int] counts;
foreach(num; myArray) {
     counts[num]++;
}

int mostFrequent;
uint maxCount = 0;
foreach(num, count; counts) {
    if(count > maxCount) { 
        mostFrequent = num;
        maxCount = count;
    }
}