在v_JULY_v的文章中找到了这个问题的解法后用C++实现了一下,发现C++的代码非常的简洁。
主要用到了标准库中的hash_map,优先级队列priority_queue。
算法的思路是:
- 从头到尾遍历文件,从文件中读取遍历到的每一个单词。
- 把遍历到的单词放到hash_map中,并统计这个单词出现的次数。
- 遍历hash_map,将遍历到的单词的出现次数放到优先级队列中。
- 当优先级队列的元素个数超过k个时就把元素级别最低的那个元素从队列中取出,这样始终保持队列的元素是k个。
- 遍历完hash_map,则队列中就剩下了出现次数最多的那k个元素。
具体实现和结果如下:
//出现次数最多的是个单词
//出现次数最多的是个单词 void top_k_words() { timer t; ifstream fin; fin.open("modern c.txt"); if (!fin) { cout<<"can nont open file"<<endl; } string s; hash_map<string,int> countwords; while (true) { fin>>s; if (fin.eof()) { break; } countwords[s]++; } cout<<"单词总数 (重复的不计数):"<<countwords.size()<<endl; priority_queue<pair<int,string>,vector<pair<int,string>>,greater<pair<int,string>>> countmax; for(hash_map<string,int>::const_iterator i=countwords.begin(); i!=countwords.end();i++) { countmax.push(make_pair(i->second,i->first)); if (countmax.size()>10) { countmax.pop(); } } while(!countmax.empty()) { cout<<countmax.top().second<<" "<<countmax.top().first<<endl; countmax.pop(); } cout<<"time elapsed "<<t.elapsed()<<endl; }