[問題] linear time 找到眾數
看板Prob_Solve (計算數學 Problem Solving)作者colorflags時間14年前 (2010/06/28 12:39)推噓3(3推 0噓 3→)留言6則, 4人參與討論串1/2 (看更多)
題目是有一串很長的數列
要找出出現最多次的數字
難的地方當然在要用linear time
linear time的話 一般的sorting應該就先排除了
DP 和 greedy 好像也沒有linear time的特性
實在是不知道要怎麼樣下手比較好
linear time -> go through 數列幾次就可以找到答案
1. 那應該要有一個紀錄出現最多次的數字variable或是array
並且一開始先假設第一個數字是眾數
那在我iterate到第i個數值的話
我手上的眾數一定要出現X次以上
有點像greedy 不過這條路好像行不通
因為很可能數字都出現在後面
那如果先randomize過後咧?
2. 把題目簡化成找到出現次數最多次的是出現過幾次
這好像也沒有變得比較容易....
我變不出新的想法了
懇請大家提供意見 感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.24.27.144
→
06/28 12:46, , 1F
06/28 12:46, 1F
推
06/28 14:12, , 2F
06/28 14:12, 2F
推
06/28 14:23, , 3F
06/28 14:23, 3F
→
06/28 14:23, , 4F
06/28 14:23, 4F
推
06/28 18:58, , 5F
06/28 18:58, 5F
→
06/28 18:58, , 6F
06/28 18:58, 6F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12