1
HunterPan 2013-12-27 08:58:44 +08:00
遍历一次,不用记录重复次数的。
|
2
xdeng 2013-12-27 09:08:29 +08:00
坐等 比 遍历一遍 还快的算法
|
3
yimity 2013-12-27 09:20:45 +08:00 3
开始遍历,例如 2,遍历的时候,判断下一个和上一个是否相等,如果相等(例如都是2),count + 1,,此时需要遍历6此。否则,从下一个(也就是3)直接跳过 count 个,如果跳过之后的下一个不是3,那么肯定3的长度就没有2的多喽,但是如果还是3,那么继续遍历,并且 count+1,此时2 的长度肯定就比3小了,以此类推。
|
4
sgissb1 2013-12-27 09:24:58 +08:00
这个数列很像kmp算法介绍时的那个数列。
我感觉他是不是想要类似kmp的做法。 |
6
tearsinchina 2013-12-27 09:27:02 +08:00 1
按照去掉重复的数字的算法,遍历一遍,留下的就是重复次数最多
|
7
vainly 2013-12-27 09:28:49 +08:00 2
Map(Integer,Integer)
if(have) count+1 else map.put(list(i),1) |
8
txx 2013-12-27 09:30:23 +08:00
常数优化么?不可能有比O(N)更快的算法了吧?
如果再做就只能做贪心 跳一下了... |
11
xunyu 2013-12-27 09:37:12 +08:00 1
抽样
|
12
moondark 2013-12-27 09:37:53 +08:00 2
@yimity
扫描第一个,得到 数字 2 出现次数6, 然后从3开始,每次跳跃的步数以6开始,如果,下标加6之后看是不是3,如果是,从当前下标数3的次数,大于次数6,则更新最大次数 如果不是,顺序扫描到 1 的下标。。 这样,最坏的情况是O(n)(即例子上,出现次数最多的是第一组),最好的情况是一直以当前最大出现次数进行跳跃。 我也想到的是这个 |
14
Actrace 2013-12-27 09:41:08 +08:00
老老实实遍历.
|
15
holmesabc 2013-12-27 09:42:16 +08:00
|
16
Hyperion 2013-12-27 09:46:23 +08:00
|
17
action 2013-12-27 09:48:40 +08:00
3l正解
|
18
justfindu 2013-12-27 09:48:56 +08:00 1
|
19
Hyperion 2013-12-27 09:52:42 +08:00 1
[2,2,2,2,2,2],3,3,3,3,1,1,1,5,1,1,1,1,1,1,1
扫描, 得出2的序列长度是6. 2,2,2,2,2,2,[3,3,3,3,1,1],1,5,1,1,1,1,1,1,1 扫描, 头尾3-1, 不匹配. 2,2,2,2,2,2,3,3,3,3,[1,1,1,5,1,1],1,1,1,1,1 逆向搜索, 找到1的序列起始位置, 扫描6个. 头尾1-1, 匹配成功, 但要确认. ==> 2,2,2,2,2,2,3,3,3,3,[1,1,1,5,1,1],1,1,1,1,1 =>> 头尾一样, 逆向确认, 发现1不是连续的, 放弃. 2,2,2,2,2,2,3,3,3,3,1,1,1,5,[1,1,1,1,1,1],1 逆向搜索, 找到1的序列起始位置, 扫描6个. 头尾1-1, 匹配成功, 确认. ==> 2,2,2,2,2,2,3,3,3,3,1,1,1,5,[1,1,1,1,1,1,1] =>> 头尾一样, 逆向确认, 发现1是连续的, 确认下1的长度. 得出1的序列长度7. 好像没什么问题耶. |
22
rrfeng 2013-12-27 09:56:16 +08:00
|
23
little_cup 2013-12-27 09:56:16 +08:00 via Android 2
在3l的基础上如果不是,2分来定位。
|
24
xujialiang OP 大家都好机智~~~
|
25
Hyperion 2013-12-27 10:01:47 +08:00
@xujialiang 永远没有面试官机智... 面试官出的题, 答案永远都是那么机智...
|
28
collar 2013-12-27 10:10:15 +08:00
3l+16l 应该是面试官想要的机智。。。。好机智。。。
|
29
Hyperion 2013-12-27 10:24:08 +08:00
@cxe2v 最坏情况, 基本应该还是O(n). 我应该没有算错吧...
@madmen 题目... 唉反正就对着题目做, 从@xujialiang 描述的面试官的话里揣摩得出的结论. 其实#19有一点错误 按照题目来说, 我后增改的部分是有问题的. 不应该出现两次1的连续序列. 统计会有大问题. 2,2,2,2,2,2,3,3,3,3,1,1,1,5,1,1,1,1,1,1,1 应该把例子改成: 2,2,2,2,2,2,3,3,3,3,1,1,1,5,6,6,6,6,6,6,6 局限那是非常之大... 其实这个算法已经变成了: 搜索最长连续序列... |
30
RIcter 2013-12-27 10:37:52 +08:00
for i in set(list):
n = n if n>list.count(i) else list.count(n) |
31
RIcter 2013-12-27 10:38:32 +08:00
...缩进呢,前面应该还有个n=0..
|
32
forestkeeper 2013-12-27 10:52:33 +08:00 1
int count = 0;
int num = 0; for (int i = 0; i<n; ++i) if (count == 0) num = a[i], count = 1; else if (num == a[i]) ++count; else --count; return [count,num] |
33
forestkeeper 2013-12-27 10:54:14 +08:00
记录重复次数的做法,如果用map,会有logm(m=数组大小)的复杂度增益,如果用桶,会让cpu增加寻址压力,而且空间复杂度都会比较大,这题是一题经典算法题,详细见我的代码
|
34
66450146 2013-12-27 11:02:34 +08:00
“我一开始的思路是 从头到尾遍历一遍,把各个数字的重复次数记录在字典中,然后再遍历字典 找出最大次数的值,面试官让我缩短时间复杂度,然后我再写了一个”
我倒想问问这面试官这个问题怎么可能会有比 O(n) 复杂度更低的算法。。 |
36
mahone3297 2013-12-27 11:14:34 +08:00
@Hyperion 逆向扫描一遍也累,如果跳不过,还是顺序扫描吧,和你想复杂度应该也是一样
|
37
ybh37 2013-12-27 11:15:10 +08:00
单纯就上面的那个序列来说,定义一个数组代替字典,只遍历一次序列、一次数组即可。
|
39
mahone3297 2013-12-27 11:16:06 +08:00
再请教下大家。。。这个题目lz基本上定性为相同的数字,都是联系在一起的。。。
那如果是相同的数字不连续在一起呢?比如 2 3 3 5 9 7 3 2 4 1 还是找出现过的数量最多的,如何解?假如数据量很大。。。。 |
40
cxe2v 2013-12-27 11:18:36 +08:00
@forestkeeper 6,6,6,2,3,3,3这样的队列,你会返回3,1这样的结果
|
41
pagict 2013-12-27 11:28:09 +08:00
刚刚实现了一遍 欢迎各种来喷(bug 编码习惯)cpp
int maxCount(const int *nums, int length) { int max=0; int i=0; int thisNum = nums[i]; int oldNum = thisNum; while(i<length) { while(i>=0 && nums[i]==thisNum) i--;// retrospect i++; i=i+max; if (nums[i]==thisNum) { // a more number max++; while(i<length && nums[i]==thisNum) i++, max++; // to the boundary max--; } oldNum = thisNum; // save the previous number to return thisNum=nums[i]; // skip some fewer numbers, update thisNum } return oldNum; } |
42
biaobiaoqi 2013-12-27 13:07:18 +08:00
23l的思路挺好
|
43
biaobiaoqi 2013-12-27 13:13:20 +08:00
@mahone3297
没有连续分布这个特征的话问题完全不一样了,也就不是大家讨论的方向了。 这个题之所以复杂度可以优化到比遍历还小就是因为连续的特征让算法可以向前试错、推测,在某些情况下节省了扫描某几个数的时间。 试想不连续的话,无法推测整个数列,至少也得遍历或许所有数据。可以用map<int, int>存储num和对应的count,同时用maxCount和maxNum存储对应的最大的情况了。 |
44
Ultratude 2013-12-27 14:04:08 +08:00 via iPhone
用 DP 比较快吧。
|
45
xdeng 2013-12-27 14:20:50 +08:00
|
48
oldcai 2013-12-27 15:37:23 +08:00
|
49
suckli 2013-12-27 15:40:16 +08:00
3楼的方法的确是有问题的
当跳过去发现不一样的情况下,此时需要逆序倒回去,确认当前下标的数字已经出现的次数,然后继续遍历才能确认当前下标的这个数字有没有超过上一个出现次数最多的数字 这样,最坏情况下就是O(N) |
50
oldcai 2013-12-27 16:25:09 +08:00 1
|
51
duzhe0 2013-12-27 17:04:12 +08:00
不可能有小于O(n)的算法啊
|
52
moondark 2013-12-27 17:34:04 +08:00
@xdeng
嗯,这个我想过,如果会出现这种情况,只能老老实实的遍历了,没有面试官所谓的“更快”了吧,像翻字典那样,字典就是指,这一部分从a开头,过了b开头,然后c开头,不会b过后还是a |
53
oldcai 2013-12-27 18:37:04 +08:00
|
56
champage 2013-12-29 14:02:23 +08:00
相同数字连续的话 跳跃遍历+计数 会不会降低时间复杂度呢
|