先謝謝大家的回覆 很抱歉題目沒講清楚 我回去看了一次問題 發現他有寫過半數都是同一個值 我也看了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