Re: [問題] linear time 找到眾數

[colorflags ()]

先謝謝大家的回覆
很抱歉題目沒講清楚 我回去看了一次問題
發現他有寫過半數都是同一個值
我也看了element uniqueness problem而得知有nlogn upper bound
所以可以產生linear time一定有附加條件

1. 如果以題目是有限範圍內的數值的話 (ex. 1~100)
那用bucket sort 加上紀錄每個bucket 的數值應該是最妥當的辦法

2. 如果是假設此最大值有過半數的話
我朋友提供一個做法但是我搞不懂
一個變數m設為0 一開始碰到第一個數字m + 1
第二個數字和第一個一樣就再 +1 反之 -1
遇到0的話就把下一個數字假設成為眾數
最後再跑一次確定是否為眾數

這個感覺跟input怎麼排列很有關係啊
假設我的眾數和非眾數是剛好交錯排列的話
那應該就會吧10101010的一直跑不是嗎



我想...會演算法的腦袋結構應該都跟一般人不一樣o_0



※ 引述《colorflags ()》之銘言：
: 題目是有一串很長的數列
: 要找出出現最多次的數字
: 難的地方當然在要用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
推 fadingaway:第二個方法應該就是正解，因為題目保證眾數會超過一半
→ fadingaway:即使剛好一半，也可以在小修正後得到linear-time的結果
→ colorflags:謝謝你~ 不過很好奇要怎麼想出答案 這是不是不算在
→ colorflags:用某個演算法推出來的成果裡?
推 fadingaway:我是在一次演講聽到的，結果可以推到眾數佔1/k比例以上
→ fadingaway:http://tinyurl.com/282bk2v 這是該次演講的類似投影片
→ fadingaway:你可以參考第39頁 (k-iceberg)