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

[Northxw]

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

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

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

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

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

[Pastsong]

set 里没有重复的元素

[Northxw]

@Pastsong emmm... 是没有重复元素，，，

[bbm]

针对上面的 2，2，1 这个例子就是 （ 2+1 ）*2 - （ 2+2+1 ）这样就求出只出现一次的数了，原理就是让出现一次的数也出现两次，然后再减去原来的数组和

[meik2333]

set(nums) 去重，sum(set(nums)) 是所有出现过的数字的和，2 * sum(set(nums)) 是每个数字出现两次的和。

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

这个解法复杂度比异或高多了，不建议使用。

[meik2333]

还不如 return reduce(lambda x, y: x ^ y, nums)

[VDimos]

这复杂度有写算法的必要吗。。。

[Northxw]

@bbm 秒懂，谢谢。

@meik2333 秒懂，谢谢。（ PS：来自评论区北大某同学）

[Northxw]

@VDimos 那你说有的话，就没有吧。

[nathanw]

reduce 一行解决

[newtype0092]

感觉传统语言做算法题是在有限的时间和空间内尽量找出最优解法，
脚本语言是在可行的方法中找出代码量最少的解法。。。

[fsafdasfsdafsd]

这个算语言技巧吧，对算法一点益处都没有，大部分的工作语言帮你做了。

[Northxw]

@newtype0092 在一般最优下，思维最重要。


@nathanw copy that

[killaboy712]

好巧 前天我也看到这题了，论区北大某同学

[Sight4]

@newtype0092 其实脚本也是一样的，set 操作的实现类 dict，对于 python 来说其实也是空间换时间，只不过语言隐藏了很多细节而已

[ArianX]

北大某同学是什么梗

[Northxw]

@killaboy712 哈哈 缘分


@ArianX 因为这段代码出自那个北大的学生

[sudoz]

@nathanw reduce 可以一行解决，但无非就是 Python 的语法糖，实际执行效率并不高

[deming]

来个好懂的 2^2^1 = 1

int res = nums[0];
for (int i = 1; i < nums.length; i++) {
res ^= nums[i];
}
return res;

[sudoz]

这个 2 倍所有独立元素，减去原有元素，等于非重复元素的思路非常牛，很有数学技巧！
令人赏心悦目

[zclHIT]

可以扩展到其他数都出现了 X 次，只有一个数出现了一次。统计所有数字每一位中 1 出现的次数，然后每一位的次数%X，最后就得到了只出现一次的那个数