面试的时候遇到一算法题

This topic created in 4559 days ago, the information mentioned may be changed or developed.

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

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

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

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

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

遍历

复杂度

数字

54 replies • 1970-01-01 08:00:00 +08:00

HunterPan

Dec 27, 2013

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

46fo

Dec 27, 2013

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

yimity

Dec 27, 2013

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

sgissb1

Dec 27, 2013

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

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

Hyperion

Dec 27, 2013

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

tearsinchina

Dec 27, 2013

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

vainly

Dec 27, 2013

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

txx

Dec 27, 2013

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

anewg

Dec 27, 2013

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

yimity

Dec 27, 2013

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

xunyu

Dec 27, 2013

抽样

moondark

Dec 27, 2013

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

我也想到的是这个

leafgray

Dec 27, 2013

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

Actrace

Dec 27, 2013

老老实实遍历.

holmesabc

Dec 27, 2013

@yimity

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

Hyperion

Dec 27, 2013

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

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

action

Dec 27, 2013

3l正解

justfindu

Dec 27, 2013

@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

Dec 27, 2013

[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

Dec 27, 2013

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

Hyperion

Dec 27, 2013

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

rrfeng

Dec 27, 2013

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

little_cup

Dec 27, 2013 via Android

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

xujialiang

Dec 27, 2013

大家都好机智～～～

Hyperion

Dec 27, 2013

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

madmen

Dec 27, 2013

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

cxe2v

Dec 27, 2013

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

collar

Dec 27, 2013

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

Hyperion

Dec 27, 2013

@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

Dec 27, 2013

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

RIcter

Dec 27, 2013

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

forestkeeper

Dec 27, 2013

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

Dec 27, 2013

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

66450146

Dec 27, 2013

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

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

rrfeng

Dec 27, 2013

@cxe2v
不会增加啊

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

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

mahone3297

Dec 27, 2013

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

ybh37

Dec 27, 2013

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

cxe2v

Dec 27, 2013

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

mahone3297

Dec 27, 2013

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

cxe2v

Dec 27, 2013

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

pagict

Dec 27, 2013

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

Dec 27, 2013

23l的思路挺好

biaobiaoqi

Dec 27, 2013

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

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

Ultratude

Dec 27, 2013 via iPhone

用 DP 比较快吧。

46fo

Dec 27, 2013

@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

Dec 27, 2013

@yimity 好方法呀！

dalang

Dec 27, 2013

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

oldcai

PRO

Dec 27, 2013

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

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

suckli

Dec 27, 2013

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

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

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

oldcai

PRO

Dec 27, 2013

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

duzhe0

Dec 27, 2013

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

moondark

Dec 27, 2013

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

oldcai

PRO

Dec 27, 2013

@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

Dec 27, 2013

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

rrfeng

Dec 27, 2013

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

champage

Dec 29, 2013

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