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

问个算法方面的问题

  •  
  •   john990 · 2014-05-15 20:07:03 +08:00 · 3011 次点击
    这是一个创建于 3844 天前的主题,其中的信息可能已经有所发展或是发生改变。
    现有一百万个数(无规律,可重复),把这些数复制一份,发现多了一个(一百万零一个),怎么用最快的方法找到多了什么数?
    22 条回复    2014-05-17 00:16:15 +08:00
    skydiver
        1
    skydiver  
       2014-05-15 20:11:07 +08:00   ❤️ 1
    异或
    dennisyang
        2
    dennisyang  
       2014-05-15 20:25:24 +08:00
    分块hash?
    john990
        3
    john990  
    OP
       2014-05-15 20:35:31 +08:00
    @skydiver 能详细点吗?
    @dennisyang 这个是今天的面试题,我也是这么说的,面试的人说有更简单的。
    skydiver
        4
    skydiver  
       2014-05-15 20:41:07 +08:00
    @john990 所有的数字异或到一起。重复的数字异或到一起就变成0了,剩下的就是多出来的数。
    这是一个经典的面试题啊。。
    john990
        5
    john990  
    OP
       2014-05-15 20:59:26 +08:00
    @skydiver oh,明白了,谢谢了,看来算法是硬伤啊
    skydiver
        6
    skydiver  
       2014-05-15 21:21:48 +08:00
    @john990 这个题基本也考不了什么能力,知道就是知道,不知道就是不知道……拿这个题考人的公司感觉不怎么靠谱……
    bengol
        7
    bengol  
       2014-05-15 21:26:00 +08:00
    为什么会多了一个?
    john990
        8
    john990  
    OP
       2014-05-15 21:34:40 +08:00
    @bengol x^x=0,x^0=x ;那两百万个数中任意一个数都是偶数个,所以异或到最后就剩下多出来的那个
    YouXia
        9
    YouXia  
       2014-05-15 21:37:02 +08:00
    @skydiver 基本上G,M等家都问这种数学类型的题目。
    txx
        10
    txx  
       2014-05-15 21:47:47 +08:00
    jsonline
        11
    jsonline  
       2014-05-16 00:05:39 +08:00
    对啊,为什么会多一个,搞清楚这个问题价值会更大吧。
    wy315700
        12
    wy315700  
       2014-05-16 00:16:47 +08:00
    把所有的数异或一下 最后的结果就是那个多出来的数
    简单的面试题
    stevenyou
        13
    stevenyou  
       2014-05-16 09:31:01 +08:00   ❤️ 1
    sum(一百万零一个) - sum(一百万个数)

    得到的结果就是多的那一个
    stevenyou
        14
    stevenyou  
       2014-05-16 09:31:51 +08:00
    效率是O(n)
    john990
        15
    john990  
    OP
       2014-05-16 09:49:35 +08:00   ❤️ 1
    @stevenyou 嗯,好办法
    cassyfar
        16
    cassyfar  
       2014-05-16 10:29:58 +08:00   ❤️ 1
    @stevenyou 有overflow的风险
    @john990
    stevenyou
        17
    stevenyou  
       2014-05-16 10:55:40 +08:00   ❤️ 1
    @cassyfar 是有overflow的问题,但是从两个数可以看出来的。如果是32bit int
    sum(一百万零一个) = -32768
    sum(一百万个数) = 32767
    可以知道多出的那个数是1

    当然了,xor的方法是最好的。
    stevenyou
        18
    stevenyou  
       2014-05-16 10:56:32 +08:00
    @cassyfar sorry , 16bit int
    cassyfar
        19
    cassyfar  
       2014-05-16 12:30:36 +08:00   ❤️ 1
    @stevenyou 对啊 但是如果overflow之后又overflow就麻烦了 毕竟100万个数的和是个很大的和
    riaqn
        20
    riaqn  
       2014-05-16 12:39:37 +08:00   ❤️ 2
    @cassyfar
    @stevenyou
    实际上 overflow 没有影响,2's complement 表示的整数是个阿贝尔群。
    以下代码在 32bit 上运行, sizeof(int)=4

    ➜ ~ cat test.c
    #include <stdio.h>
    int main() {
    int a = 1234567890;
    int b = 2134567890;
    printf("%d\n", a + b);
    printf("%d\n", a + b - a);
    }
    ➜ ~ gcc -o test test.c
    ➜ ~ ./test
    -925831516
    2134567890
    cassyfar
        21
    cassyfar  
       2014-05-16 12:53:55 +08:00
    @stevenyou 确实没影响 只要差值保留住就可以了 和overflow多少次无关
    Virtao
        22
    Virtao  
       2014-05-17 00:16:15 +08:00
    之前V2EX上就有个类似的题目,再次分享我的总结:

    http://blog.virtao.org/articles/163.html

    另外严重同意 @skydiver 的说法,这类题目玩玩可以,当面试题没意义。万一碰到个大牛恰好这个题目没碰到过呢?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2583 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 01:51 · PVG 09:51 · LAX 17:51 · JFK 20:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.