计算统计模式 [英] Computing the statistical mode

问题描述

我目前正在核实与否，考虑长度为N的无序数组A和整数K，是否存在发生N / K倍以上的一些元素。

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.

我的想法对这个问题是计算模式，然后比较这对N / K。但是，我不知道如何快速计算这种模式。我的最终结果必须是的n * log（K），但我不知道真的就如何做到这一点。我能找到的最快为：N * K ...

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 n*log(k), but I have no idea really on how to do this. The quickest I could find was n*k...

推荐答案

使用哈希表来计算每个值的频率：

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

这篇关于计算统计模式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！