计算统计模式

Question

我目前正在尝试验证是否存在长度为N且整数为k的未排序数组A,是否存在一些发生n/k次或更多次的元素.

我对这个问题的想法是计算模式,然后将其与n/k进行比较.但是,我不知道如何快速计算这种模式.我的最终结果需要是n log(k),但我真的不知道如何做到这一点.我能找到的最快的是 ......

Answer 1

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

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

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