V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Northxw
V2EX  ›  程序员

LeetCode 刷题 - 136.只出现一次的数字

  •  2
     
  •   Northxw · 2019-03-26 13:55:11 +08:00 · 4837 次点击
    这是一个创建于 1829 天前的主题,其中的信息可能已经有所发展或是发生改变。

      题目描述:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。举个例子:

    输入: [2,2,1]
    输出: 1
    

      题简单,做一遍异或就出来了。思维很重要,这不,评论区翻出了一个我认为牛逼的 Python 解法:

    return 2*sum(set(nums))-sum(nums)
    

      我想知道,这是什么原理啊! 小弟搞不清楚,请教啦。

    41 条回复    2019-06-03 19:31:58 +08:00
    Pastsong
        1
    Pastsong  
       2019-03-26 13:58:17 +08:00
    set 里没有重复的元素
    Northxw
        2
    Northxw  
    OP
       2019-03-26 14:00:21 +08:00
    @Pastsong emmm... 是没有重复元素,,,
    bbm
        3
    bbm  
       2019-03-26 14:00:48 +08:00 via iPhone
    针对上面的 2,2,1 这个例子就是 ( 2+1 )*2 - ( 2+2+1 )这样就求出只出现一次的数了,原理就是让出现一次的数也出现两次,然后再减去原来的数组和
    meik2333
        4
    meik2333  
       2019-03-26 14:00:59 +08:00   ❤️ 6
    set(nums) 去重,sum(set(nums)) 是所有出现过的数字的和,2 * sum(set(nums)) 是每个数字出现两次的和。

    2 * sum(set(nums)) - sum(nums) 就是“每个数字出现两次 - (除了某个元素只出现一次以外,其余每个元素均出现两次)”,差值就是只出现一次的那个数字。

    这个解法复杂度比异或高多了,不建议使用。
    meik2333
        5
    meik2333  
       2019-03-26 14:05:16 +08:00   ❤️ 2
    还不如 return reduce(lambda x, y: x ^ y, nums)
    VDimos
        6
    VDimos  
       2019-03-26 14:05:31 +08:00 via Android
    这复杂度有写算法的必要吗。。。
    Northxw
        7
    Northxw  
    OP
       2019-03-26 14:08:25 +08:00
    @bbm 秒懂,谢谢。

    @meik2333 秒懂,谢谢。( PS:来自评论区北大某同学)
    Northxw
        8
    Northxw  
    OP
       2019-03-26 14:09:11 +08:00
    @VDimos 那你说有的话,就没有吧。
    nathanw
        9
    nathanw  
       2019-03-26 14:24:09 +08:00 via iPhone
    reduce 一行解决
    newtype0092
        10
    newtype0092  
       2019-03-26 14:32:53 +08:00   ❤️ 2
    感觉传统语言做算法题是在有限的时间和空间内尽量找出最优解法,
    脚本语言是在可行的方法中找出代码量最少的解法。。。
    fsafdasfsdafsd
        11
    fsafdasfsdafsd  
       2019-03-26 14:35:38 +08:00
    这个算语言技巧吧,对算法一点益处都没有,大部分的工作语言帮你做了。
    Northxw
        12
    Northxw  
    OP
       2019-03-26 14:36:47 +08:00
    @newtype0092 在一般最优下,思维最重要。


    @nathanw copy that
    killaboy712
        13
    killaboy712  
       2019-03-26 15:51:55 +08:00
    好巧 前天我也看到这题了,论区北大某同学
    Sight4
        14
    Sight4  
       2019-03-26 16:20:43 +08:00
    @newtype0092 其实脚本也是一样的,set 操作的实现类 dict,对于 python 来说其实也是空间换时间,只不过语言隐藏了很多细节而已
    ArianX
        15
    ArianX  
       2019-03-26 16:51:06 +08:00 via Android
    北大某同学是什么梗
    Northxw
        16
    Northxw  
    OP
       2019-03-26 17:16:03 +08:00
    @killaboy712 哈哈 缘分


    @ArianX 因为这段代码出自那个北大的学生
    sudoz
        17
    sudoz  
       2019-03-26 17:22:32 +08:00
    @nathanw reduce 可以一行解决,但无非就是 Python 的语法糖,实际执行效率并不高
    deming
        18
    deming  
       2019-03-26 17:23:03 +08:00
    来个好懂的 2^2^1 = 1

    int res = nums[0];
    for (int i = 1; i < nums.length; i++) {
    res ^= nums[i];
    }
    return res;
    sudoz
        19
    sudoz  
       2019-03-26 17:23:46 +08:00
    这个 2 倍所有独立元素,减去原有元素,等于非重复元素的思路非常牛,很有数学技巧!
    令人赏心悦目
    zclHIT
        20
    zclHIT  
       2019-03-26 17:29:35 +08:00   ❤️ 1
    可以扩展到其他数都出现了 X 次,只有一个数出现了一次。统计所有数字每一位中 1 出现的次数,然后每一位的次数%X,最后就得到了只出现一次的那个数
    Banxiaozhuan
        21
    Banxiaozhuan  
       2019-03-26 17:34:28 +08:00
    int ans = 0;
    for (int i = 0 ; i != nums.size() ; ++i)
    ans ^= nums[i];
    return ans...
    异或足矣。
    Greendays
        22
    Greendays  
       2019-03-26 17:35:54 +08:00
    感觉像小学鸡兔同笼的思路 233
    ArianX
        23
    ArianX  
       2019-03-26 17:44:07 +08:00 via Android
    @zclHIT 可是这样复杂度不就变成 O(m * n) 了么。leetcode 上另一个类似的题好像是用有限状态机解决的,复杂度仍是 O(n)
    Northxw
        24
    Northxw  
    OP
       2019-03-26 17:51:22 +08:00
    @ArianX @Greendays @Banxiaozhuan @zclHIT @sudoz @deming 说真心的,我比较喜欢人家这种另类的思维。思维很重要。。。。
    22k
        25
    22k  
       2019-03-26 18:20:35 +08:00
    反正像我这种菜鸡也就只能看看复制粘贴然后理解一下就完事的了
    guiqiqi
        26
    guiqiqi  
       2019-03-26 18:28:18 +08:00 via iPhone
    我就想问为啥没人提异或
    guiqiqi
        27
    guiqiqi  
       2019-03-26 18:31:15 +08:00 via iPhone
    @guiqiqi 没看描述……不好意思
    Banxiaozhuan
        28
    Banxiaozhuan  
       2019-03-26 18:38:21 +08:00
    @Northxw 我再想一个问题。。。。 会不会溢出? 不过看不出有什么好的思维。
    Northxw
        29
    Northxw  
    OP
       2019-03-26 19:00:10 +08:00
    @Banxiaozhuan 应该不会溢出吧。。。
    Justin13
        30
    Justin13  
       2019-03-26 19:06:03 +08:00 via Android
    思路不错,但是作为算法不合格。
    enenaaa
        31
    enenaaa  
       2019-03-26 19:22:28 +08:00
    @Banxiaozhuan 不会,python 的整型支持无限长度, 不是 32 位,64 位的。
    Xs0ul
        32
    Xs0ul  
       2019-03-27 00:24:05 +08:00
    异或的亮点不就是 o(1)空间复杂度吗?如果 set 都用了,那还不如直接循环一遍不在里面就加,在里面就删掉,或者干脆用 dict 计数。有种杀鸡用牛刀的感觉
    Northxw
        33
    Northxw  
    OP
       2019-03-27 07:43:23 +08:00
    @Justin13 嗯,有点嫌疑。


    @Xs0ul 哈哈,重在思维过程。
    ofooo
        34
    ofooo  
       2019-03-27 10:42:40 +08:00
    @Xs0ul 至少得遍历一遍吧?怎么可能 O(1)复杂度呢? 还有不用 set 怎么解?
    zclHIT
        35
    zclHIT  
       2019-03-27 11:01:50 +08:00
    @Northxw 放入 set 其实更费时间,不信你试试。。。
    forestLittleBear
        36
    forestLittleBear  
       2019-03-27 11:20:27 +08:00
    萌新搞不懂了。。异或不是返回 0 或者 1 嘛。。。f(f(2,2),1)为啥就把 1 找出来了。。。。
    Northxw
        37
    Northxw  
    OP
       2019-03-27 12:37:02 +08:00
    @forestLittleBear 异或的规则:二进制相同位的位置做异或,相同的话异或结果为 0,不同的话异或结果为 1. 然后你按着这个思路,做一遍异或,就知道了。
    Xs0ul
        38
    Xs0ul  
       2019-03-27 21:22:13 +08:00
    @ofooo #34 O(1)是“空间”复杂度。不用 set 就用异或呀,大家很多层都讨论了
    TIKA
        39
    TIKA  
       2019-05-10 01:31:24 +08:00
    这个解法让我想起了一种鸡兔同笼的问题解法,跟这个类似
    siliconMagic
        40
    siliconMagic  
       2019-05-10 09:23:23 +08:00
    先假设全部成对出现,计算和,然后减去实际的的 sum,多出来的那个就是单独的元素
    lanshee
        41
    lanshee  
       2019-06-03 19:31:58 +08:00
    捋了下,不管是 sum 的还是位运算的,感觉就是成双成对的情侣里面有一个是单身汉,而情人节到了,情侣都去约会开房去了,最后剩下了那个单身汉.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3378 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 13:15 · PVG 21:15 · LAX 06:15 · JFK 09:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.