这是一个创建于 2394 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。举个例子：
输入: [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