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

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

  •  2
     
  •   Northxw · 144 天前 · 3522 次点击
    这是一个创建于 144 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

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

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

    这个解法复杂度比异或高多了,不建议使用。
        5
    meik2333   144 天前   ♥ 2
    还不如 return reduce(lambda x, y: x ^ y, nums)
        6
    VDimos   144 天前 via Android
    这复杂度有写算法的必要吗。。。
        7
    Northxw   144 天前
    @bbm 秒懂,谢谢。

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


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


    @ArianX 因为这段代码出自那个北大的学生
        17
    sudoz   144 天前
    @nathanw reduce 可以一行解决,但无非就是 Python 的语法糖,实际执行效率并不高
        18
    deming   144 天前
    来个好懂的 2^2^1 = 1

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


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