Re: [問題] 統計string中單字出現的次數

[holymars ()]

用兩個set..

std::set< std::pair<std::string, int>* >

第一個set依照字串排序　第二個set依照count排序
input進來全部丟進第一個set計算count
輸入完之後把第一個set的內容全部丟到第二個set
第二個set的end()就是答案..

這種東西...基本上就是砍一半的bimap
如果可以用library的話　boost::bimap或是boost::multi_index
都是不錯的選擇..
前者比較好學　介面比較明確　　後者比較泛用

※ 引述《jehovah (Lucius)》之銘言：
: 小弟不才..又來求教一練習題
: 題目要求由使用者輸入字串
: 並輸出各單字中出現最頻繁者和次數
: 例如 how, now now brown cow
: 則得到 now : 2
: 我目前只會硬幹將單字丟入vector中, 並將每個單字與所有單字做比對
:     string s;
:     vector<string> v;
:     while(cin>>s)
:     v.push_back(s);                     //vector存各個單字
:     int* cptr = new int[v.size()]();    //array存各個單字的次數
:     for(vector<string>::size_type ix=0; ix!=v.size(); ++ix)
:         for(vector<string>::size_type iy=0; iy!=v.size(); ++iy)
:         {
:             if(v[ix] == v[iy])
:             cptr[ix]++;
:         }
: 這樣子是能記錄各個單字的次數 how, now now brown cow
:                          cptr[0]  [1] [2]  [3]  [4]
:                               1    2   2    1    1
: 再從次數找最大值, 之後用index代回vector得到單字..
: 如果單字一樣就擇其一輸出
: 只是這樣子比對複雜度是O(n^2), 輸入多一點就很沒效率
: 完全是硬湊出來的解法@@
: 能否提供我一些方向或提示..該怎麼思考這樣的問題比較好?
: 謝謝!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.136.184.87
→ holymars:喔對了　如果有hash_set可以用　第一個set應該用hash
→ holymars:multi_index本身就有hash_index就是了XD
推 loveme00835:set::end() 回傳的迭代器不可取值的喔~
→ holymars:啊..我是要寫back()　囧　不過set好像也沒back()
→ holymars:總之就是最後count最大的那個element~"~
→ holymars:*(--end())...
→ holymars:再不然反過來排　那begin()就是答案啦XD
→ holymars:啊.....突然想到最後一個element不就是rbegin()嗎 我昏了
→ yoco315:大家都很常忘記 rbegin