面试的时候遇到一算法题

[xujialiang]

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

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

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

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

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

[Hyperion]

@cxe2v 正常谁会这么干(不排除)... 跳过一点是一点... 面试题总是这么没道理- -

[rrfeng]

@holmesabc
@justfindu
@Hyperion
@leafgray
跳过其他数没问题的吧？假设 n(2)=6；既然从第一个 3 起跳，6 次之后如果不是 3 那么说明 n(3) < n(2) ，被跳过的必然小于 6 ，只需要回退到当前数字的第一个就行了，然后再跳

[little_cup]

在3l的基础上如果不是，2分来定位。

[xujialiang]

大家都好机智～～～

[Hyperion]

@xujialiang 永远没有面试官机智... 面试官出的题, 答案永远都是那么机智...

[madmen]

@Hyperion 你的思路有前提，前提是一定是有连续重复，如果没有呢？ 那哪来的效率...

[cxe2v]

@rrfeng 这样不光时间复杂度增加了，算法复杂度也增加了

[collar]

3l+16l 应该是面试官想要的机智。。。。好机智。。。

[Hyperion]

@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

局限那是非常之大... 其实这个算法已经变成了: 搜索最长连续序列...

[RIcter]

for i in set(list):
n = n if n>list.count(i) else list.count(n)

[RIcter]

...缩进呢，前面应该还有个n=0..

[forestkeeper]

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]

[forestkeeper]

记录重复次数的做法，如果用map，会有logm（m＝数组大小）的复杂度增益，如果用桶，会让cpu增加寻址压力，而且空间复杂度都会比较大，这题是一题经典算法题，详细见我的代码

[66450146]

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

我倒想问问这面试官这个问题怎么可能会有比 O(n) 复杂度更低的算法。。

[rrfeng]

@cxe2v
不会增加啊

计数，比较，逆序遍历，跳跃

比完整遍历一遍计算量没增加，遍历量减少了

[mahone3297]

@Hyperion 逆向扫描一遍也累，如果跳不过，还是顺序扫描吧，和你想复杂度应该也是一样

[ybh37]

单纯就上面的那个序列来说，定义一个数组代替字典，只遍历一次序列、一次数组即可。

[cxe2v]

@66450146 12楼已经给出时间复杂度可能会小于O(N)的算法，只不过操作起来比较复杂而已

[mahone3297]

再请教下大家。。。这个题目lz基本上定性为相同的数字，都是联系在一起的。。。
那如果是相同的数字不连续在一起呢？比如 2 3 3 5 9 7 3 2 4 1
还是找出现过的数量最多的，如何解？假如数据量很大。。。。

[cxe2v]

@forestkeeper 6,6,6,2,3,3,3这样的队列，你会返回3,1这样的结果