Re: [問題] 關於眾數問題

看板C_and_CPP作者 (XOO)時間15年前 (2010/10/22 05:24), 編輯推噓11(11推 0噓 26→)
留言37則, 3人參與, 最新討論串3/3 (看更多)
※ 引述《yauhh (喲)》之銘言： : ※ 引述《applea123 (小刀)》之銘言： : : 最近在寫眾數問題 : : 主要是考慮到眾數>2時 : : ex:1 1 1 1 1 2 2 2 2 3 3 3 4 4 : : 眾數有1 2 : : 次數4 : : 我自己是有寫出來 但是想問問大家有沒更快的"想法" : : 我的步驟: : : 1.排序 並丟入a[] : : 2.用一個陣列b[]紀錄各數出現次數並使用另一個對應陣列c[]來記錄此數字 : : 3.陣列b排列並且c一起做交換 : : 4.判斷b[] if(b[i]=b[i+1]) : : 5.印出b[] 與c[] : 我的作法沒很快,很基本: : 一直線掃描,看過的數字把頻次加一,沒看過的數字填入表中. 啊哈, 如果考慮的有界整數, 考慮 bucket sort 的變形就好 想法跟你一樣, 但如果知道上下界的話, 直接開一個固定大小的 array X, 假設是 0 - 99, 看到 0 就在 X[0] 加一, 線性時間內就解決了。 要找眾數就等同於找這個 array 上的最大值們。排序也可以順便完成， 照頻率表上的數字填回去就好。 -- XOO's http://xcycl.wordpress.com/ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 147.188.193.87
→
10/22 09:07, , 1F
嗯!沒錯
10/22 09:07, 1F
推
10/22 12:11, , 2F
把問題簡化成這樣當然好做, 多來幾個 INT_MAX, 然後數
10/22 12:11, 2F
→
10/22 12:11, , 3F
字種類不多, 這樣的線性...
10/22 12:11, 3F
推
10/23 00:23, , 4F
想了很久用兩個Map來轉 http://codepad.org/9rWLJfi4
10/23 00:23, 4F
推
10/23 00:46, , 5F
如果是這個做法我會用 map + priority_queue 喔 XD
10/23 00:46, 5F
推
10/23 00:49, , 6F
XD
10/23 00:49, 6F
→
10/23 00:50, , 7F
速度的差別嗎?
10/23 00:50, 7F
推
10/23 01:15, , 8F
heap & RB tree 的速度這情況下應該是沒差多少, 不過
10/23 01:15, 8F
→
10/23 01:16, , 9F
我不確定 end() 回傳的迭代器是不是屬於Bidirectional
10/23 01:16, 9F
→
10/23 01:17, , 10F
Iterator, 最好還是用 rbegin 會比較好, 我會選用
10/23 01:17, 10F
→
10/23 01:18, , 11F
priority_queue 的原因是因為他的介面很簡單, 我只需
10/23 01:18, 11F
→
10/23 01:18, , 12F
自訂比大小的方法, 就可以等著一直取最大的元素出來,
10/23 01:18, 12F
→
10/23 01:19, , 13F
而不必去記從哪邊取, 或是作key-value互換的動作
10/23 01:19, 13F
推
10/23 01:34, , 14F
我是覺得還要多寫比較方法以及紀錄眾數及次數是什麼
10/23 01:34, 14F
→
10/23 01:35, , 15F
會比較麻煩一點，就直接用第二個map開工拉XD
10/23 01:35, 15F
推
10/23 01:36, , 16F
記住次數就好了說@_@ 看個人喜好囉~
10/23 01:36, 16F
→
10/23 01:36, , 17F
map的iter是bidirectional沒錯，--是因為past the end
10/23 01:36, 17F
→
10/23 01:36, , 18F
你也太快回文= =
10/23 01:36, 18F
→
10/23 01:37, , 19F
不, pass the end 不是指他真的在最後一個元素之後,
10/23 01:37, 19F
→
10/23 01:38, , 20F
那只是一個概念, 雖然在vector裡真的是如此, 但在list
10/23 01:38, 20F
→
10/23 01:38, , 21F
中, 或是 istream_iterator 來講, 都有可能是一個特別
10/23 01:38, 21F
→
10/23 01:39, , 22F
的數值, 像是 NULL, 頂多只能當作標兵, 而不能用它來
10/23 01:39, 22F
→
10/23 01:39, , 23F
作往回移的效果
10/23 01:39, 23F
推
10/23 01:41, , 24F
打錯字 pass → past
10/23 01:41, 24F
推
10/23 01:44, , 25F
我知道她是一個概念，畢竟rb tree要說最後一個元素很怪
10/23 01:44, 25F
→
10/23 01:45, , 26F
而回傳的是bidirectional iter便代表可以--囉!
10/23 01:45, 26F
→
10/23 01:45, , 27F
在sgi stl的pre condition內有寫到
10/23 01:45, 27F
→
10/23 01:45, , 28F
i is dereferenceable or past-the-end. There exists
10/23 01:45, 28F
→
10/23 01:46, , 29F
a dereferenceable iterator j such that i == ++j.
10/23 01:46, 29F
推
10/23 01:48, , 30F
如果回傳的是BidirectionalIterator, 就表示可以--,
10/23 01:48, 30F
→
10/23 01:49, , 31F
那你知道 past the end 本來就違反 dereferencable 這
10/23 01:49, 31F
→
10/23 01:50, , 32F
個操作嗎? 你上面那句話只是說明 pass the end 是 rea
10/23 01:50, 32F
→
10/23 01:50, , 33F
chable 並沒有說 從 past the end 還可以回來
10/23 01:50, 33F
→
10/23 02:10, , 34F
找到了, 規格書中 24.1.4 的 Table 75 的第一列寫到
10/23 02:10, 34F
→
10/23 02:12, , 35F
--i 的情況, 當有一個 dereferencable 的迭代器 s, 使
10/23 02:12, 35F
→
10/23 02:13, , 36F
得 r == ++s, 那 --r 就是合法的
10/23 02:13, 36F
推
10/23 12:20, , 37F
規格書你是上網買嗎XD?iterator的用法就此打住吧
10/23 12:20, 37F
‣ 更多 xcycl 的文章
文章代碼(AID): #1CmAzmRz (C_and_CPP)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共3篇)
‣ 更多 xcycl 的文章
文章代碼(AID): #1CmAzmRz (C_and_CPP)