面试的时候遇到一算法题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 4315 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

遍历

复杂度

数字

54 条回复 1970-01-01 08:00:00 +08:00

HunterPan

2013-12-27 08:58:44 +08:00

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

xdeng

2013-12-27 09:08:29 +08:00

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

yimity

2013-12-27 09:20:45 +08:00

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

sgissb1

2013-12-27 09:24:58 +08:00

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

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

Hyperion

2013-12-27 09:25:39 +08:00

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

tearsinchina

2013-12-27 09:27:02 +08:00

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

vainly

2013-12-27 09:28:49 +08:00

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

txx

2013-12-27 09:30:23 +08:00

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

anewg

2013-12-27 09:34:24 +08:00

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

yimity

2013-12-27 09:35:52 +08:00

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

xunyu

2013-12-27 09:37:12 +08:00

抽样

moondark

2013-12-27 09:37:53 +08:00

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

我也想到的是这个

leafgray

2013-12-27 09:39:09 +08:00

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

Actrace

2013-12-27 09:41:08 +08:00

老老实实遍历.

holmesabc

2013-12-27 09:42:16 +08:00

@yimity

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

Hyperion

2013-12-27 09:46:23 +08:00

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

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

action

2013-12-27 09:48:40 +08:00

3l正解

justfindu

2013-12-27 09:48:56 +08:00

@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

2013-12-27 09:52:42 +08:00

[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

2013-12-27 09:53:54 +08:00

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

Hyperion

2013-12-27 09:55:37 +08:00

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

rrfeng

2013-12-27 09:56:16 +08:00

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

little_cup

2013-12-27 09:56:16 +08:00 via Android

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

xujialiang

2013-12-27 09:57:01 +08:00

大家都好机智～～～

Hyperion

2013-12-27 10:01:47 +08:00

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

madmen

2013-12-27 10:03:39 +08:00

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

cxe2v

2013-12-27 10:07:44 +08:00

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

collar

2013-12-27 10:10:15 +08:00

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

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

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

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)

RIcter

2013-12-27 10:38:32 +08:00

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

forestkeeper

2013-12-27 10:52:33 +08:00

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

2013-12-27 10:54:14 +08:00

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

66450146

2013-12-27 11:02:34 +08:00

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

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

&nbp; 35

rrfeng

2013-12-27 11:02:34 +08:00

@cxe2v
不会增加啊

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

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

mahone3297

2013-12-27 11:14:34 +08:00

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

ybh37

2013-12-27 11:15:10 +08:00

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

cxe2v

2013-12-27 11:15:19 +08:00

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

mahone3297

2013-12-27 11:16:06 +08:00

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

cxe2v

2013-12-27 11:18:36 +08:00

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

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;
}

biaobiaoqi

2013-12-27 13:07:18 +08:00

23l的思路挺好

biaobiaoqi

2013-12-27 13:13:20 +08:00

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

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

Ultratude

2013-12-27 14:04:08 +08:00 via iPhone

用 DP 比较快吧。

xdeng

2013-12-27 14:20:50 +08:00

@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

2013-12-27 14:36:48 +08:00

@yimity 好方法呀！

dalang

2013-12-27 15:17:52 +08:00

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

oldcai

PRO

2013-12-27 15:37:23 +08:00

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

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

suckli

2013-12-27 15:40:16 +08:00

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

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

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

oldcai

PRO

2013-12-27 16:25:09 +08:00

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

duzhe0

2013-12-27 17:04:12 +08:00

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

moondark

2013-12-27 17:34:04 +08:00

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

oldcai

PRO

2013-12-27 18:37:04 +08:00

@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

PRO

2013-12-27 19:43:06 +08:00

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

rrfeng

2013-12-27 20:48:06 +08:00

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

champage

2013-12-29 1:02:23 +08:00

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