V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
xujialiang
V2EX  ›  问与答

面试的时候遇到一算法题

  •  
  •   xujialiang · 2013-12-27 08:54:26 +08:00 · 5084 次点击
    这是一个创建于 3966 天前的主题,其中的信息可能已经有所发展或是发生改变。
    题目是这样:
    有一个队列,比方说是: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
        1
    HunterPan  
       2013-12-27 08:58:44 +08:00
    遍历一次,不用记录重复次数的。
    xdeng
        2
    xdeng  
       2013-12-27 09:08:29 +08:00
    坐等 比 遍历一遍 还快的算法
    yimity
        3
    yimity  
       2013-12-27 09:20:45 +08:00   ❤️ 3
    开始遍历,例如 2,遍历的时候,判断下一个和上一个是否相等,如果相等(例如都是2),count + 1,,此时需要遍历6此。否则,从下一个(也就是3)直接跳过 count 个,如果跳过之后的下一个不是3,那么肯定3的长度就没有2的多喽,但是如果还是3,那么继续遍历,并且 count+1,此时2 的长度肯定就比3小了,以此类推。
    sgissb1
        4
    sgissb1  
       2013-12-27 09:24:58 +08:00
    这个数列很像kmp算法介绍时的那个数列。

    我感觉他是不是想要类似kmp的做法。
    Hyperion
        5
    Hyperion  
       2013-12-27 09:25:39 +08:00
    @yimity = = 好机智的做法...
    tearsinchina
        6
    tearsinchina  
       2013-12-27 09:27:02 +08:00   ❤️ 1
    按照去掉重复的数字的算法,遍历一遍,留下的就是重复次数最多
    vainly
        7
    vainly  
       2013-12-27 09:28:49 +08:00   ❤️ 2
    Map(Integer,Integer)
    if(have) count+1
    else
    map.put(list(i),1)
    txx
        8
    txx  
       2013-12-27 09:30:23 +08:00
    常数优化么?不可能有比O(N)更快的算法了吧?
    如果再做就只能做贪心 跳一下了...
    anewg
        9
    anewg  
       2013-12-27 09:34:24 +08:00
    @yimity 这个不行吧,跳的区间内有除3以外的别的数要怎么计数?
    yimity
        10
    yimity  
       2013-12-27 09:35:52 +08:00
    @anewg 这个是有问题,但是有其他数的话,其长度也肯定没有2的长把。不过有其他问题。
    xunyu
        11
    xunyu  
       2013-12-27 09:37:12 +08:00   ❤️ 1
    抽样
    moondark
        12
    moondark  
       2013-12-27 09:37:53 +08:00   ❤️ 2
    @yimity
    扫描第一个,得到 数字 2 出现次数6,
    然后从3开始,每次跳跃的步数以6开始,如果,下标加6之后看是不是3,如果是,从当前下标数3的次数,大于次数6,则更新最大次数
    如果不是,顺序扫描到 1 的下标。。
    这样,最坏的情况是O(n)(即例子上,出现次数最多的是第一组),最好的情况是一直以当前最大出现次数进行跳跃。

    我也想到的是这个
    leafgray
        13
    leafgray  
       2013-12-27 09:39:09 +08:00
    @yimity
    2,2,3,5,5,5,1 中间count跳过了其它的数了。。。
    Actrace
        14
    Actrace  
       2013-12-27 09:41:08 +08:00
    老老实实遍历.
    holmesabc
        15
    holmesabc  
       2013-12-27 09:42:16 +08:00
    @yimity

    跳过后是3还好,不是3就有问题了。
    比如是1,这时是不知道跳过了几个1。
    暂时只能说3没2多,但不能说其它数不比2多。
    Hyperion
        16
    Hyperion  
       2013-12-27 09:46:23 +08:00
    @moondark @yimity 跳跃之后, 匹配成功时候还要加一步确认, 逆向扫一遍, 确认区间内, 数字序列是不是连续的.

    进行下一次跳跃的起始位置, 应该是在当前跳跃位置的那个数字序列的头部...
    action
        17
    action  
       2013-12-27 09:48:40 +08:00
    3l正解
    justfindu
        18
    justfindu  
       2013-12-27 09:48:56 +08:00   ❤️ 1
    @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
        19
    Hyperion  
       2013-12-27 09:52:42 +08:00   ❤️ 1
    [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
        20
    cxe2v  
       2013-12-27 09:53:54 +08:00
    @Hyperion 你逆向扫描一遍不是又花时间了,还不如遍历一次来得稳定和快速
    Hyperion
        21
    Hyperion  
       2013-12-27 09:55:37 +08:00
    @cxe2v 正常谁会这么干(不排除)... 跳过一点是一点... 面试题总是这么没道理- -
    rrfeng
        22
    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
        23
    little_cup  
       2013-12-27 09:56:16 +08:00 via Android   ❤️ 2
    在3l的基础上如果不是,2分来定位。
    xujialiang
        24
    xujialiang  
    OP
       2013-12-27 09:57:01 +08:00
    大家都好机智~~~
    Hyperion
        25
    Hyperion  
       2013-12-27 10:01:47 +08:00
    @xujialiang 永远没有面试官机智... 面试官出的题, 答案永远都是那么机智...
    madmen
        26
    madmen  
       2013-12-27 10:03:39 +08:00
    @Hyperion 你的思路有前提,前提是一定是有连续重复,如果没有呢? 那哪来的效率...
    cxe2v
        27
    cxe2v  
       2013-12-27 10:07:44 +08:00
    @rrfeng 这样不光时间复杂度增加了,算法复杂度也增加了
    collar
        28
    collar  
       2013-12-27 10:10:15 +08:00
    3l+16l 应该是面试官想要的机智。。。。好机智。。。
    Hyperion
        29
    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
        30
    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
        31
    RIcter  
       2013-12-27 10:38:32 +08:00
    ...缩进呢,前面应该还有个n=0..
    forestkeeper
        32
    forestkeeper  
       2013-12-27 10:52:33 +08:00   ❤️ 1
    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
        33
    forestkeeper  
       2013-12-27 10:54:14 +08:00
    记录重复次数的做法,如果用map,会有logm(m=数组大小)的复杂度增益,如果用桶,会让cpu增加寻址压力,而且空间复杂度都会比较大,这题是一题经典算法题,详细见我的代码
    66450146
        34
    66450146  
       2013-12-27 11:02:34 +08:00
    “我一开始的思路是 从头到尾遍历一遍,把各个数字的重复次数记录在字典中,然后再遍历字典 找出最大次数的值,面试官让我缩短时间复杂度,然后我再写了一个”

    我倒想问问这面试官这个问题怎么可能会有比 O(n) 复杂度更低的算法。。
    rrfeng
        35
    rrfeng  
       2013-12-27 11:02:34 +08:00
    @cxe2v
    不会增加啊

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

    比完整遍历一遍计算量没增加,遍历量减少了
    mahone3297
        36
    mahone3297  
       2013-12-27 11:14:34 +08:00
    @Hyperion 逆向扫描一遍也累,如果跳不过,还是顺序扫描吧,和你想复杂度应该也是一样
    ybh37
        37
    ybh37  
       2013-12-27 11:15:10 +08:00
    单纯就上面的那个序列来说,定义一个数组代替字典,只遍历一次序列、一次数组即可。
    cxe2v
        38
    cxe2v  
       2013-12-27 11:15:19 +08:00
    @66450146 12楼已经给出时间复杂度可能会小于O(N)的算法,只不过操作起来比较复杂而已
    mahone3297
        39
    mahone3297  
       2013-12-27 11:16:06 +08:00
    再请教下大家。。。这个题目lz基本上定性为相同的数字,都是联系在一起的。。。
    那如果是相同的数字不连续在一起呢?比如 2 3 3 5 9 7 3 2 4 1
    还是找出现过的数量最多的,如何解?假如数据量很大。。。。
    cxe2v
        40
    cxe2v  
       2013-12-27 11:18:36 +08:00
    @forestkeeper 6,6,6,2,3,3,3这样的队列,你会返回3,1这样的结果
    pagict
        41
    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
        42
    biaobiaoqi  
       2013-12-27 13:07:18 +08:00
    23l的思路挺好
    biaobiaoqi
        43
    biaobiaoqi  
       2013-12-27 13:13:20 +08:00
    @mahone3297
    没有连续分布这个特征的话问题完全不一样了,也就不是大家讨论的方向了。
    这个题之所以复杂度可以优化到比遍历还小就是因为连续的特征让算法可以向前试错、推测,在某些情况下节省了扫描某几个数的时间。

    试想不连续的话,无法推测整个数列,至少也得遍历或许所有数据。可以用map<int, int>存储num和对应的count,同时用maxCount和maxNum存储对应的最大的情况了。
    Ultratude
        44
    Ultratude  
       2013-12-27 14:04:08 +08:00 via iPhone
    用 DP 比较快吧。
    xdeng
        45
    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
        46
    teddy1004  
       2013-12-27 14:36:48 +08:00
    @yimity 好方法呀!
    dalang
        47
    dalang  
       2013-12-27 15:17:52 +08:00
    @yimity 应该是最快的方法了。
    oldcai
        48
    oldcai  
       2013-12-27 15:37:23 +08:00
    @yimity
    @moondark
    如果是已排序好的,跳过已有最大步长,是可行的。

    @xdeng
    @dalang
    除了这个优化,其实还可以有二倍法延长步长,而不是一直n++。
    suckli
        49
    suckli  
       2013-12-27 15:40:16 +08:00
    3楼的方法的确是有问题的

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

    这样,最坏情况下就是O(N)
    oldcai
        50
    oldcai  
       2013-12-27 16:25:09 +08:00   ❤️ 1
    duzhe0
        51
    duzhe0  
       2013-12-27 17:04:12 +08:00
    不可能有小于O(n)的算法啊
    moondark
        52
    moondark  
       2013-12-27 17:34:04 +08:00
    @xdeng
    嗯,这个我想过,如果会出现这种情况,只能老老实实的遍历了,没有面试官所谓的“更快”了吧,像翻字典那样,字典就是指,这一部分从a开头,过了b开头,然后c开头,不会b过后还是a
    oldcai
        53
    oldcai  
       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
        54
    oldcai  
       2013-12-27 19:43:06 +08:00
    @moondark 又想了一下,是我自作聪明了。
    如果有不是在一起的相同数字,确实就不能跳过任何数字,就必须得O(n)
    rrfeng
        55
    rrfeng  
       2013-12-27 20:48:06 +08:00
    @xdeng 相同的数字是连续的,不会被分开,前面说明白了吧。
    如果完全混杂的话,那么直接遍历用3个变量来计数就行了
    champage
        56
    champage  
       2013-12-29 14:02:23 +08:00
    相同数字连续的话 跳跃遍历+计数 会不会降低时间复杂度呢
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5046 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 03:56 · PVG 11:56 · LAX 19:56 · JFK 22:56
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.