面试的时候遇到一算法题

[xujialiang]

题目是这样：
有一个队列,比方说是：2，2，2，2，2，2，3，3，3，3，3，1，1，1，5，5，5，5

然后让你找出数字中重复最多的一个数字。

我一开始的思路是 从头到尾遍历一遍，把各个数字的重复次数记录在字典中，然后再遍历字典 找出最大次数的值，面试官让我缩短时间复杂度，然后我再写了一个

第二次的思路是 定义两个变量存放最数字和重复次数 从头到尾遍历一遍即可。 面试官说，能不能再缩短时间复杂度，比方说我们翻字典，不用一页一页找，当时没回答上来。他说有兴趣 可以自己再去看看。

今天想了下，因为它一类的一定是在一起的，那么那么我遍历的时候，可以跳跃，不用一个个去遍历， 这样 时间复杂度必然有缩短，不知大家还有其它的思路不？

[HunterPan]

遍历一次，不用记录重复次数的。

[xdeng]

坐等 比 遍历一遍 还快的算法

[yimity]

开始遍历，例如 2，遍历的时候，判断下一个和上一个是否相等，如果相等（例如都是2），count + 1，，此时需要遍历6此。否则，从下一个（也就是3）直接跳过 count 个，如果跳过之后的下一个不是3，那么肯定3的长度就没有2的多喽，但是如果还是3，那么继续遍历，并且 count+1，此时2 的长度肯定就比3小了，以此类推。

[sgissb1]

这个数列很像kmp算法介绍时的那个数列。

我感觉他是不是想要类似kmp的做法。

[Hyperion]

@yimity = = 好机智的做法...

[tearsinchina]

按照去掉重复的数字的算法，遍历一遍，留下的就是重复次数最多

[vainly]

Map(Integer,Integer)
if(have) count+1
else
map.put(list(i),1)

[txx]

常数优化么？不可能有比O(N)更快的算法了吧？
如果再做就只能做贪心 跳一下了...

[anewg]

@yimity 这个不行吧，跳的区间内有除3以外的别的数要怎么计数？

[yimity]

@anewg 这个是有问题，但是有其他数的话，其长度也肯定没有2的长把。不过有其他问题。

[xunyu]

抽样

[moondark]

@yimity
扫描第一个，得到 数字 2 出现次数6，
然后从3开始，每次跳跃的步数以6开始，如果，下标加6之后看是不是3，如果是，从当前下标数3的次数，大于次数6，则更新最大次数
如果不是，顺序扫描到 1 的下标。。
这样，最坏的情况是O（n）（即例子上，出现次数最多的是第一组），最好的情况是一直以当前最大出现次数进行跳跃。

我也想到的是这个

[leafgray]

@yimity
2,2,3,5,5,5,1 中间count跳过了其它的数了。。。

[Actrace]

老老实实遍历.

[holmesabc]

@yimity

跳过后是3还好，不是3就有问题了。
比如是1,这时是不知道跳过了几个1。
暂时只能说3没2多，但不能说其它数不比2多。

[Hyperion]

@moondark @yimity 跳跃之后, 匹配成功时候还要加一步确认, 逆向扫一遍, 确认区间内, 数字序列是不是连续的.

进行下一次跳跃的起始位置, 应该是在当前跳跃位置的那个数字序列的头部...

[action]

3l正解

[justfindu]

@leafgray 跳过其他数没有问题的~ 只是如果跳到了某个数中间~ 如

2 2 2 2 2 2 3 3 5 6 6 6 6 6 6 6

2 有6 个, 到3时候直接比较之后6个, 应该是6 不一样,这时候应该往回再数, 直到数到5,
@moondark
@yimity

[Hyperion]

[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.

好像没什么问题耶.

[cxe2v]

@Hyperion 你逆向扫描一遍不是又花时间了，还不如遍历一次来得稳定和快速