请教优化算法问题:统计数组中成员出现的频率

Question

数组原始状态是空的,然后成员1个个的被加入(成千上万的成员),现在要找出出现频率最高的30个成员,请问有什么好的算法吗?一个一个遍历是不是太慢了,需要快速的方法阿,请教高手.《数据结构》好像有这样的解决方法，请大家指点下

Answer 1

有一个数组,里面有成千上万的元素,像这样:array A={"red","blue","orange","blue"……}怎样快速的统计出这个数组中出现频率最高的30个元素呢？速度优先，不考虑空间开支，谢谢

Answer 2

std::map<std::string,int> count;
for (int i=0;i<array.size();i++)
{
    count[array[i]]++;
}
然后取count 前30个

Answer 3

我覺得樓上說得很清楚了，當然最後排序也可以省掉，因爲在輸入的同時進行統計也可以進行排序。比如最初你每個元素的數目分別是
0，0，0，0
一次輸入以後變成
0，1，0，0
這時直接在變化以後排一次序就可以
不考慮空間 就可以做成一個map 就可以避免出現的元素種類太多的情況了

Answer 4

std::map<std::string,int> count;
cin >> array[i];
count[array[i]++];
尽量要省略排序查找等
也可以建堆,