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

看板C_and_CPP作者 (Lucius)時間15年前 (2010/09/05 16:57), 編輯推噓8(8025)
留言33則, 4人參與, 最新討論串1/4 (看更多)
小弟不才..又來求教一練習題 題目要求由使用者輸入字串 並輸出各單字中出現最頻繁者和次數 例如 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

09/06 01:01, , 1F
直覺是sort之後找equal_range或count...XD
09/06 01:01, 1F

09/06 01:02, , 2F
雖然big-O會簡少 但是不保證會變快XDD
09/06 01:02, 2F

09/06 01:05, , 3F
話說你這樣寫會把"how,"和"how"當成不同的字...
09/06 01:05, 3F

09/06 01:09, , 4F
是啊.. 還在想辦法去掉標點才存.. 見笑了:)
09/06 01:09, 4F

09/06 01:10, , 5F
我是想可以用getline加上find_first_(not_)of的delim來做
09/06 01:10, 5F

09/06 01:40, , 6F
boost::bimap或boost::multi_index
09/06 01:40, 6F

09/06 01:47, , 7F
考試來不及灌boost..(誤
09/06 01:47, 7F

09/06 01:57, , 8F
remove_if, istringstream, istream_iterator,
09/06 01:57, 8F

09/06 01:57, , 9F
multiset, count
09/06 01:57, 9F

09/06 02:16, , 10F
用multiset跟vector+sort一樣平均都是nlogn 但是我記得不
09/06 02:16, 10F

09/06 02:16, , 11F
會比較快的說...
09/06 02:16, 11F

09/06 02:31, , 12F
如果有M個詞每個次出現N次 你全塞進去再sort
09/06 02:31, 12F

09/06 02:32, , 13F
是MNlog(MN)...你丟進set或map算count是MNlog(M)
09/06 02:32, 13F

09/06 02:34, , 14F
再來用equal_range找答案是Mlog(MN)..set是Mlog(M)
09/06 02:34, 14F

09/06 02:35, , 15F
空間複雜度vector+sort是MN set是M
09/06 02:35, 15F

09/06 02:37, , 16F
但是每次insert時同樣要耗logn不是嗎..加起來也是nlogn@@?
09/06 02:37, 16F

09/06 02:38, , 17F
沒有啊 insert的時侯只是把count++而已
09/06 02:38, 17F

09/06 02:38, , 18F
我記得1+2+...+logn會等於logn..演算法離我很遙遠XD
09/06 02:38, 18F

09/06 02:39, , 19F
在set中找到那個詞是log(M),把count++,一共要做MN次
09/06 02:39, 19F

09/06 02:39, , 20F
所以是MNlog(M)
09/06 02:39, 20F

09/06 02:40, , 21F
哦哦 我指的是love大的multiset 不是您說的那個啦
09/06 02:40, 21F

09/06 02:42, , 22F
喔喔...multiset確實沒有比較快...
09/06 02:42, 22F

09/06 02:45, , 23F
我考慮的只是將每個物件的生命週期減短, 把所有工作都
09/06 02:45, 23F

09/06 02:46, , 24F
您的方法的確比較快又省空間 跟我的直覺不能比啊 哈哈
09/06 02:46, 24F

09/06 02:46, , 25F
丟給ctor來達成exception safety, 速度那麼重要也不用
09/06 02:46, 25F

09/06 02:46, , 26F
物件來寫了啊...
09/06 02:46, 26F

09/06 02:48, , 27F
是啊 所以說big-O減少不一定效率較高XD 用更primitive的
09/06 02:48, 27F

09/06 02:49, , 28F
寫法還有很多東西可以加速..我想只是提個結構上的速度而已
09/06 02:49, 28F

09/06 02:50, , 29F
這..如果MN都是10000,你的方法就是慢100倍 這不是效率
09/06 02:50, 29F

09/06 02:50, , 30F
問題 是演算法問題啊XDDD
09/06 02:50, 30F

09/06 02:54, , 31F
用multiset的意思就是 同一個字出現100次 就會存100次
09/06 02:54, 31F

09/06 02:54, , 32F
但是你把一段一樣的字串存100次下來有什麼意思呢..
09/06 02:54, 32F

09/06 02:58, , 33F
所言甚是 = =
09/06 02:58, 33F
文章代碼(AID): #1CWyllZs (C_and_CPP)
討論串 (同標題文章)
文章代碼(AID): #1CWyllZs (C_and_CPP)