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

[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: 218.162.80.111
→ hilorrk:直覺是sort之後找equal_range或count...XD
→ hilorrk:雖然big-O會簡少　但是不保證會變快XDD
→ hilorrk:話說你這樣寫會把"how,"和"how"當成不同的字...
→ jehovah:是啊.. 還在想辦法去掉標點才存.. 見笑了:)
→ hilorrk:我是想可以用getline加上find_first_(not_)of的delim來做
推 holymars:boost::bimap或boost::multi_index
→ hilorrk:考試來不及灌boost..(誤
推 loveme00835:remove_if, istringstream, istream_iterator,
→ loveme00835:multiset, count
→ hilorrk:用multiset跟vector+sort一樣平均都是nlogn　但是我記得不
→ hilorrk:會比較快的說...
推 holymars:如果有M個詞每個次出現N次　你全塞進去再sort
→ holymars:是MNlog(MN)...你丟進set或map算count是MNlog(M)
→ holymars:再來用equal_range找答案是Mlog(MN)..set是Mlog(M)
→ holymars:空間複雜度vector+sort是MN set是M
→ hilorrk:但是每次insert時同樣要耗logn不是嗎..加起來也是nlogn@@?
推 holymars:沒有啊　insert的時侯只是把count++而已
→ hilorrk:我記得1+2+...+logn會等於logn..演算法離我很遙遠XD
→ holymars:在set中找到那個詞是log(M)，把count++，一共要做MN次
→ holymars:所以是MNlog(M)
→ hilorrk:哦哦　我指的是love大的multiset　不是您說的那個啦
推 holymars:喔喔...multiset確實沒有比較快...
推 loveme00835:我考慮的只是將每個物件的生命週期減短, 把所有工作都
→ hilorrk:您的方法的確比較快又省空間　跟我的直覺不能比啊　哈哈
→ loveme00835:丟給ctor來達成exception safety, 速度那麼重要也不用
→ loveme00835:物件來寫了啊...
→ hilorrk:是啊　所以說big-O減少不一定效率較高XD 用更primitive的
→ hilorrk:寫法還有很多東西可以加速..我想只是提個結構上的速度而已
推 holymars:這..如果MN都是10000，你的方法就是慢100倍　這不是效率
→ holymars:問題　是演算法問題啊XDDD
推 holymars:用multiset的意思就是　同一個字出現100次　就會存100次
→ holymars:但是你把一段一樣的字串存100次下來有什麼意思呢..
→ loveme00835:所言甚是 =  =