[問題] linear time 找到眾數

[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
→ tkcn:開陣列，空間換時間。或用 hash table。
推 ledia:if the value range is fixed and small, use counting sort
推 FRAXIS:你想要找的眾數 有說要出現次數超過n/2次嘛？
→ FRAXIS:還是只是出現最多次的元素？
推 fadingaway:這個問題在comparison model下有Ω(nlgn)的lower bound
→ fadingaway:參考: element uniqueness problem