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

[Northxw]

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

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

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

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

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

[Banxiaozhuan]

int ans = 0;
for (int i = 0 ; i != nums.size() ; ++i)
ans ^= nums[i];
return ans...
异或足矣。

[Greendays]

感觉像小学鸡兔同笼的思路 233

[ArianX]

@zclHIT 可是这样复杂度不就变成 O(m * n) 了么。leetcode 上另一个类似的题好像是用有限状态机解决的，复杂度仍是 O(n)

[Northxw]

@ArianX @Greendays @Banxiaozhuan @zclHIT @sudoz @deming 说真心的，我比较喜欢人家这种另类的思维。思维很重要。。。。

[22k]

反正像我这种菜鸡也就只能看看复制粘贴然后理解一下就完事的了

[guiqiqi]

我就想问为啥没人提异或

[guiqiqi]

@guiqiqi 没看描述……不好意思

[Banxiaozhuan]

@Northxw 我再想一个问题。。。。 会不会溢出？ 不过看不出有什么好的思维。

[Northxw]

@Banxiaozhuan 应该不会溢出吧。。。

[Justin13]

思路不错，但是作为算法不合格。

[enenaaa]

@Banxiaozhuan 不会，python 的整型支持无限长度， 不是 32 位，64 位的。

[Xs0ul]

异或的亮点不就是 o(1)空间复杂度吗？如果 set 都用了，那还不如直接循环一遍不在里面就加，在里面就删掉，或者干脆用 dict 计数。有种杀鸡用牛刀的感觉

[Northxw]

@Justin13 嗯，有点嫌疑。


@Xs0ul 哈哈，重在思维过程。

[ofooo]

@Xs0ul 至少得遍历一遍吧？怎么可能 O(1)复杂度呢？ 还有不用 set 怎么解？

[zclHIT]

@Northxw 放入 set 其实更费时间，不信你试试。。。

[forestLittleBear]

萌新搞不懂了。。异或不是返回 0 或者 1 嘛。。。f(f(2,2),1)为啥就把 1 找出来了。。。。

[Northxw]

@forestLittleBear 异或的规则：二进制相同位的位置做异或，相同的话异或结果为 0，不同的话异或结果为 1. 然后你按着这个思路，做一遍异或，就知道了。

[Xs0ul]

@ofooo #34 O(1)是“空间”复杂度。不用 set 就用异或呀，大家很多层都讨论了

[TIKA]

这个解法让我想起了一种鸡兔同笼的问题解法，跟这个类似

[siliconMagic]

先假设全部成对出现，计算和，然后减去实际的的 sum，多出来的那个就是单独的元素