题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。举个例子：
输入: [2,2,1]
输出: 1
题简单，做一遍异或就出来了。思维很重要，这不，评论区翻出了一个我认为牛逼的 Python 解法：
return 2*sum(set(nums))-sum(nums)
我想知道，这是什么原理啊！ 小弟搞不清楚，请教啦。
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 2780 days ago, the information mentioned may be changed or developed.
 |
PastsongMar 26, 2019
1
set 里没有重复的元素
|
 |
bbmMar 26, 2019 via iPhone
3
针对上面的 2，2，1 这个例子就是 （ 2+1 ）*2 - （ 2+2+1 ）这样就求出只出现一次的数了，原理就是让出现一次的数也出现两次，然后再减去原来的数组和
|
 |
4
set(nums) 去重，sum(set(nums)) 是所有出现过的数字的和，2 * sum(set(nums)) 是每个数字出现两次的和。
2 * sum(set(nums)) - sum(nums) 就是“每个数字出现两次 - （除了某个元素只出现一次以外，其余每个元素均出现两次）”，差值就是只出现一次的那个数字。 这个解法复杂度比异或高多了，不建议使用。 |
6 |
5
还不如 return reduce(lambda x, y: x ^ y, nums)
|
 |
VDimosMar 26, 2019 via Android
6
这复杂度有写算法的必要吗。。。
|
 |
nathanwMar 26, 2019 via iPhone
9
reduce 一行解决
|
 |
10
感觉传统语言做算法题是在有限的时间和空间内尽量找出最优解法，
脚本语言是在可行的方法中找出代码量最少的解法。。。 |
 |
fsafdasfsdafsdMar 26, 2019
11
这个算语言技巧吧，对算法一点益处都没有，大部分的工作语言帮你做了。
|
 |
12
|
 |
killaboy712Mar 26, 2019
13
好巧 前天我也看到这题了，论区北大某同学
|
 |
Sight4Mar 26, 2019
14
@newtype0092 其实脚本也是一样的，set 操作的实现类 dict，对于 python 来说其实也是空间换时间，只不过语言隐藏了很多细节而已
|
 |
ArianXMar 26, 2019 via Android
15
北大某同学是什么梗
|
|
16
|
 |
demingMar 26, 2019
18
来个好懂的 2^2^1 = 1
int res = nums[0]; for (int i = 1; i < nums.length; i++) { res ^= nums[i]; } return res; |
 |
sudozMar 26, 2019
19
这个 2 倍所有独立元素，减去原有元素，等于非重复元素的思路非常牛，很有数学技巧！
令人赏心悦目 |
 |
20
可以扩展到其他数都出现了 X 次，只有一个数出现了一次。统计所有数字每一位中 1 出现的次数，然后每一位的次数%X，最后就得到了只出现一次的那个数
|
 |
BanxiaozhuanMar 26, 2019
21
int ans = 0;
for (int i = 0 ; i != nums.size() ; ++i) ans ^= nums[i]; return ans... 异或足矣。 |
 |
GreendaysMar 26, 2019
22
感觉像小学鸡兔同笼的思路 233
|
|
ArianXMar 26, 2019 via Android
23
@zclHIT 可是这样复杂度不就变成 O(m * n) 了么。leetcode 上另一个类似的题好像是用有限状态机解决的，复杂度仍是 O(n)
|
|
24
|
 |
22kMar 26, 2019
25
反正像我这种菜鸡也就只能看看复制粘贴然后理解一下就完事的了
|
 |
guiqiqiMar 26, 2019 via iPhone
26
我就想问为啥没人提异或
|
|
BanxiaozhuanMar 26, 2019
28
@Northxw 我再想一个问题。。。。 会不会溢出？ 不过看不出有什么好的思维。
|
|
29
@Banxiaozhuan 应该不会溢出吧。。。
|
 |
Justin13Mar 26, 2019 via Android
30
思路不错，但是作为算法不合格。
|
 |
enenaaaMar 26, 2019
31
@Banxiaozhuan 不会，python 的整型支持无限长度， 不是 32 位，64 位的。
|
 |
Xs0ulMar 27, 2019
32
异或的亮点不就是 o(1)空间复杂度吗？如果 set 都用了，那还不如直接循环一遍不在里面就加，在里面就删掉，或者干脆用 dict 计数。有种杀鸡用牛刀的感觉
|
 |
forestLittleBearMar 27, 2019
36
萌新搞不懂了。。异或不是返回 0 或者 1 嘛。。。f(f(2,2),1)为啥就把 1 找出来了。。。。
|
|
37
@forestLittleBear 异或的规则：二进制相同位的位置做异或，相同的话异或结果为 0，不同的话异或结果为 1. 然后你按着这个思路，做一遍异或，就知道了。
|
 |
TIKAMay 10, 2019
39
这个解法让我想起了一种鸡兔同笼的问题解法，跟这个类似
|
 |
siliconMagicMay 10, 2019
40
先假设全部成对出现，计算和，然后减去实际的的 sum，多出来的那个就是单独的元素
|
 |
lansheeJun 3, 2019
41
捋了下,不管是 sum 的还是位运算的,感觉就是成双成对的情侣里面有一个是单身汉,而情人节到了,情侣都去约会开房去了,最后剩下了那个单身汉.
|
Select Language