作者colorflags ()
站内Prob_Solve
标题[问题] linear time 找到众数
时间Mon Jun 28 12:39:06 2010
题目是有一串很长的数列
要找出出现最多次的数字
难的地方当然在要用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
1F：→ tkcn:开阵列，空间换时间。或用 hash table。 06/28 12:46
2F：推 ledia:if the value range is fixed and small, use counting sort 06/28 14:12
3F：推 FRAXIS:你想要找的众数 有说要出现次数超过n/2次嘛？ 06/28 14:23
4F：→ FRAXIS:还是只是出现最多次的元素？ 06/28 14:23
5F：推 fadingaway:这个问题在comparison model下有Ω(nlgn)的lower bound 06/28 18:58
6F：→ fadingaway:参考: element uniqueness problem 06/28 18:58