PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者colorflags時間14年前 (2010/06/29 09:41)推噓2(2推 0噓 5→)

留言7則, 2人參與討論串2/2 (看更多)

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