先谢谢大家的回覆 很抱歉题目没讲清楚 我回去看了一次问题 发现他有写过半数都是同一个值 我也看了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