这是一个创建于 2105 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。举个例子：
输入: [2,2,1]
输出: 1
题简单，做一遍异或就出来了。思维很重要，这不，评论区翻出了一个我认为牛逼的 Python 解法：
return 2*sum(set(nums))-sum(nums)
我想知道，这是什么原理啊！ 小弟搞不清楚，请教啦。
 |
1
Pastsong 2019-03-26 13:58:17 +08:00
set 里没有重复的元素
|
 |
3
bbm 2019-03-26 14:00:48 +08:00 via iPhone
针对上面的 2，2，1 这个例子就是 （ 2+1 ）*2 - （ 2+2+1 ）这样就求出只出现一次的数了，原理就是让出现一次的数也出现两次，然后再减去原来的数组和
|
 |
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) 就是“每个数字出现两次 - （除了某个元素只出现一次以外，其余每个元素均出现两次）”，差值就是只出现一次的那个数字。 这个解法复杂度比异或高多了，不建议使用。 |
|
5
meik2333 2019-03-26 14:05:16 +08:00 2
还不如 return reduce(lambda x, y: x ^ y, nums)
|
 |
6
VDimos 2019-03-26 14:05:31 +08:00 via Android
这复杂度有写算法的必要吗。。。
|
 |
9
nathanw 2019-03-26 14:24:09 +08:00 via iPhone
reduce 一行解决
|
 |
10
newtype0092 2019-03-26 14:32:53 +08:00 2
感觉传统语言做算法题是在有限的时间和空间内尽量找出最优解法，
脚本语言是在可行的方法中找出代码量最少的解法。。。 |
 |
11
fsafdasfsdafsd 2019-03-26 14:35:38 +08:00
这个算语言技巧吧，对算法一点益处都没有，大部分的工作语言帮你做了。
|
 |
12
Northxw OP |
 |
13
killaboy712 2019-03-26 15:51:55 +08:00
好巧 前天我也看到这题了，论区北大某同学
|
 |
14
Sight4 2019-03-26 16:20:43 +08:00
@newtype0092 其实脚本也是一样的，set 操作的实现类 dict，对于 python 来说其实也是空间换时间，只不过语言隐藏了很多细节而已
|
 |
15
ArianX 2019-03-26 16:51:06 +08:00 via Android
北大某同学是什么梗
|
|
16
Northxw OP |
 |
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; |
 |
19
sudoz 2019-03-26 17:23:46 +08:00
这个 2 倍所有独立元素，减去原有元素，等于非重复元素的思路非常牛，很有数学技巧！
令人赏心悦目 |
 |
20
zclHIT 2019-03-26 17:29:35 +08:00 1
可以扩展到其他数都出现了 X 次，只有一个数出现了一次。统计所有数字每一位中 1 出现的次数，然后每一位的次数%X，最后就得到了只出现一次的那个数
|
 |
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... 异或足矣。 |
 |
22
Greendays 2019-03-26 17:35:54 +08:00
感觉像小学鸡兔同笼的思路 233
|
|
23
ArianX 2019-03-26 17:44:07 +08:00 via Android
@zclHIT 可是这样复杂度不就变成 O(m * n) 了么。leetcode 上另一个类似的题好像是用有限状态机解决的，复杂度仍是 O(n)
|
|
24
Northxw OP |
 |
25
22k 2019-03-26 18:20:35 +08:00
反正像我这种菜鸡也就只能看看复制粘贴然后理解一下就完事的了
|
 |
26
guiqiqi 2019-03-26 18:28:18 +08:00 via iPhone
我就想问为啥没人提异或
|
|
28
Banxiaozhuan 2019-03-26 18:38:21 +08:00
@Northxw 我再想一个问题。。。。 会不会溢出？ 不过看不出有什么好的思维。
|
|
29
Northxw OP @Banxiaozhuan 应该不会溢出吧。。。
|
 |
30
Justin13 2019-03-26 19:06:03 +08:00 via Android
思路不错，但是作为算法不合格。
|
 |
31
enenaaa 2019-03-26 19:22:28 +08:00
@Banxiaozhuan 不会，python 的整型支持无限长度， 不是 32 位，64 位的。
|
 |
32
Xs0ul 2019-03-27 00:24:05 +08:00
异或的亮点不就是 o(1)空间复杂度吗？如果 set 都用了，那还不如直接循环一遍不在里面就加，在里面就删掉，或者干脆用 dict 计数。有种杀鸡用牛刀的感觉
|
 |
36
forestLittleBear 2019-03-27 11:20:27 +08:00
萌新搞不懂了。。异或不是返回 0 或者 1 嘛。。。f(f(2,2),1)为啥就把 1 找出来了。。。。
|
|
37
Northxw OP @forestLittleBear 异或的规则：二进制相同位的位置做异或，相同的话异或结果为 0，不同的话异或结果为 1. 然后你按着这个思路，做一遍异或，就知道了。
|
 |
39
TIKA 2019-05-10 01:31:24 +08:00
这个解法让我想起了一种鸡兔同笼的问题解法，跟这个类似
|
 |
40
siliconMagic 2019-05-10 09:23:23 +08:00
先假设全部成对出现，计算和，然后减去实际的的 sum，多出来的那个就是单独的元素
|
 |
41
lanshee 2019-06-03 19:31:58 +08:00
捋了下,不管是 sum 的还是位运算的,感觉就是成双成对的情侣里面有一个是单身汉,而情人节到了,情侣都去约会开房去了,最后剩下了那个单身汉.
|
Select Language