arrays - 查找数组中第 N 个最频繁数字的算法

Question

我想编写一个算法来查找数组中第 n 个出现频率最高的数字。我有一个解决方案但不是最优的(我已经测试过的测试数字)请问有没有更优的解决方案？这是我的解决方案:

most_freq_element(a,n){
final_cnt = 0, curr_cnt = 1, final_freq_num = -1, curr_freq_num = -1;
for(i = 0; i < n-1; i++)
{
    if (a[i]!=-1){
        curr_freq_num = a[i];
        for(j =i+1; j < n; j++){
            if(curr_freq_num == a[j] && final_freq_num != curr_freq_num){
                curr_cnt++;
            }
        }
        if(final_cnt < curr_cnt){
            final_cnt = curr_cnt;
            curr_cnt = 1;
            final_freq_num = curr_freq_num;
        }
    }
}
printf("Num = %d and times = %d", final_freq_num, final_cnt);
}



nth_most_frequent_element(a,n,k){    
if(k==1){
    return most_freq_element(a,n);
}
else{ 
    for (i=0;i<k;i++){
        int most_freq_num = most_freq_element(a,n);

        for(i = 0; i < n-1; i++){
            if (a[i]==most_freq_num){
                a[i]=-1;
            }
        }
    }
    return most_freq_element(a,n);
}
}

Answer 1

我可能会制作一个散列图/表，并在发生冲突时递增每个值，这样数字就是键，值就是冲突的次数。然后，当你完成后，将它聚合到一个排序列表中并获取第 n 个元素。将在 O(n) 中运行，这是非常理想的。

编辑:实际上，排序将花费 n*log(n)。