题目描述:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。举个例子:
输入: [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 的还是位运算的,感觉就是成双成对的情侣里面有一个是单身汉,而情人节到了,情侣都去约会开房去了,最后剩下了那个单身汉.
|