面试的时候遇到一算法题

[xujialiang]

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

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

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

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

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

[pagict]

刚刚实现了一遍 欢迎各种来喷（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;
}

[biaobiaoqi]

23l的思路挺好

[biaobiaoqi]

@mahone3297
没有连续分布这个特征的话问题完全不一样了，也就不是大家讨论的方向了。
这个题之所以复杂度可以优化到比遍历还小就是因为连续的特征让算法可以向前试错、推测，在某些情况下节省了扫描某几个数的时间。

试想不连续的话，无法推测整个数列，至少也得遍历或许所有数据。可以用map<int, int>存储num和对应的count，同时用maxCount和maxNum存储对应的最大的情况了。

[Ultratude]

用 DP 比较快吧。

[xdeng]

@moondark 你们说的 2，2，2，2，2，2，3，3，3，3，3，1，1，1，5，5，5，5 计数2为6
“然后从3开始，每次跳跃的步数以6开始，如果，下标加6之后看是不是3”

如果数据是 2，2，2，2，2，2，3，3，x，x，x，3，3，1，5，5，5，5 这样 你的算法就出问题了

@cxe2v 你同意的12楼 有问题的吧

[teddy1004]

@yimity 好方法呀！

[dalang]

@yimity 应该是最快的方法了。

[oldcai]

@yimity
@moondark
如果是已排序好的，跳过已有最大步长，是可行的。

@xdeng
@dalang
除了这个优化，其实还可以有二倍法延长步长，而不是一直n++。

[suckli]

3楼的方法的确是有问题的

当跳过去发现不一样的情况下，此时需要逆序倒回去，确认当前下标的数字已经出现的次数，然后继续遍历才能确认当前下标的这个数字有没有超过上一个出现次数最多的数字

这样，最坏情况下就是O(N)

[oldcai]

https://gist.github.com/oldcai/8144123

[duzhe0]

不可能有小于O(n)的算法啊

[moondark]

@xdeng
嗯，这个我想过，如果会出现这种情况，只能老老实实的遍历了，没有面试官所谓的“更快”了吧，像翻字典那样，字典就是指，这一部分从a开头，过了b开头，然后c开头，不会b过后还是a

[oldcai]

@moondark 入50楼，去掉
if current_index + max_repeat < length \
and arr[current_index] == arr[current_index + max_repeat]:
current_index += max_repeat
二倍法
@duzhe0 最坏是O(n)，最好是O(log2(n))

[oldcai]

@moondark 又想了一下，是我自作聪明了。
如果有不是在一起的相同数字，确实就不能跳过任何数字，就必须得O(n)

[rrfeng]

@xdeng 相同的数字是连续的，不会被分开，前面说明白了吧。
如果完全混杂的话，那么直接遍历用3个变量来计数就行了

[champage]

相同数字连续的话 跳跃遍历+计数 会不会降低时间复杂度呢