这是一个创建于 2139 天前的主题，其中的信息可能已经有所发展或是发生改变。
这是一道看完答案会觉得很简单，但做之前很难想到答案的题目！！！
不信？
Let us go ！
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
题目解析
根据题目描述，由于加上了时间复杂度必须是 O(n)，并且空间复杂度为 O(1)的条件，因此不能用排序方法，也不能使用 map 数据结构。
小吴想了一下午没想出来，答案是使用 位操作 Bit Operation 来解此题。
将所有元素做异或运算，即 a[1] ⊕ a[2] ⊕ a[3] ⊕ …⊕ a[n]，所得的结果就是那个只出现一次的数字，时间复杂度为 O(n)。
异或
异或运算 A ⊕ B 的真值表如下：
| A | B | ⊕ | |:------------- |:---------------:| -------------:| | F | F | F | | F | T | T | | T | F | T | | T | T | F |
动画演示
进阶版
有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。
示例 :
输入: [1,2,2,1,3,4]
输出: [3,4]
题目再解析
根据前面找一个不同数的思路算法，在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果。
然后，因为这两个只出现一次的元素一定是不相同的，所以这两个元素的二进制形式肯定至少有某一位是不同的，即一个为 0，另一个为 1，现在需要找到这一位。
根据异或的性质 任何一个数字异或它自己都等于 0，得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。
再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。
-
将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个
-
将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。
这样就解出题目。忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为 O(n)。
动画再演示
End
本题的基础版来源于 LeetCode 第 136 号问题：只出现一次的数字。虽然题目难度是 简单，但解法真的很巧妙。感兴趣的同学可以根据思路去回答一下： https://leetcode-cn.com/problems/single-number/ 。
预防杠精，注： 思路是否拍案叫绝与此前在剑指 offer 上是否看到过此题并没有关系
原文：一道让你拍案叫绝的算法题
 |
1
Kaiv2 2019-01-16 11:35:29 +08:00
这让我想到了一道面试题，给狗狗喂药的
|
 |
2
CoderOnePolo OP @Kaiv2 100 只🐶，两瓶毒药那种吗？
|
 |
3
rrfeng 2019-01-16 11:58:51 +08:00 via Android
题目读了一半就知道是异或了…
虽然我不写算法但是看得多了套路上了 |
 |
4
aheadlead 2019-01-16 12:00:08 +08:00 via iPhone
|
 |
5
hadoop 2019-01-16 12:00:45 +08:00 via Android
这…不是常用套路吗
|
|
6
aheadlead 2019-01-16 12:03:23 +08:00 via iPhone  1
 |
 |
7
Sanko 2019-01-16 12:11:26 +08:00 via Android
leetcode 刷过这个
|
 |
8
zhujinliang 2019-01-16 12:18:28 +08:00 via iPhone
如果题目是重复出现的数字可以重复奇数次，怎么做呢？
|
 |
9
lshang 2019-01-16 12:24:07 +08:00 via Android
@zhujinliang 重复奇数次不是跟现在一样么，最终会剩下一个数字
|
 |
10
mathzhaoliang 2019-01-16 12:51:45 +08:00
@lshang 不对。你试试 [1 ,1 ,1 , 0] 这个最简单的例子。
|
 |
11
auv1107 2019-01-16 13:27:33 +08:00
虽然现在看是一道集齐普通的算法题，但当第一次看到时确实有一种拍案叫绝、醍醐灌顶之感。
|
 |
12
VoidChen 2019-01-16 13:56:54 +08:00
看了开头我就知道是异或了，这不能说巧妙，只是很多人没想起异或有这样的特性
|
 |
13
sagaxu 2019-01-16 13:57:58 +08:00 via Android
十年前就见过的套路
|
 |
14
urmyfaith 2019-01-16 14:17:00 +08:00
走过的路都是套路?
|
 |
15
felixlong 2019-01-16 14:58:29 +08:00 via Android
这样的题目只能自娱自乐啦。就像孔乙己问茴字的四种写法一样。
|
 |
16
Amit 2019-01-16 17:28:10 +08:00
动态图片是用什么工具做的？
|
 |
17
est 2019-01-16 17:34:38 +08:00
如果一个出现 3 次，其他的都出现 5 次呢。 /狗头
|
 |
18
stone666 2019-01-16 17:38:31 +08:00
让我想起了 BitMap
|
 |
19
jmc891205 2019-01-16 17:50:23 +08:00 via iPhone
写长文也就算了
居然还做了图片 lz 工作不饱和呀～ txtx |
 |
20
ayase252 2019-01-16 19:06:25 +08:00 via iPhone
用设计数字电路的办法有通解
|
 |
21
woodensail 2019-01-16 19:08:05 +08:00
[1e9,1e10,1e11]
来演示一下 |
 |
22
thedrwu 2019-01-16 19:12:39 +08:00 via Android
大家一起 xor 一下不就解决了吗。。不需要额外空间。
|
|
23
thedrwu 2019-01-16 19:14:18 +08:00 via Android
呃…只看完题目描述就抢答了。没看楼主已经给出了答案
|
 |
24
duanluray 2019-01-16 20:11:43 +08:00
leetcode 刷过，HW 的机试也做过
|
|
25
Kaiv2 2019-01-16 20:41:49 +08:00 via Android
@CoderOnePolo 1000 瓶毒药 1 瓶有毒，喂给 10 只狗狗，猜哪瓶有毒
|
 |
26
alpenstock 2019-01-17 08:34:35 +08:00
喵~
|
 |
27
qiutianaimeili 2019-01-17 08:53:33 +08:00
之前见过
|
 |
28
XuanFei990 2019-01-17 09:28:00 +08:00
都是套路。。。
之前刷了一个重复奇数次的，，最快的算法也是这种逻辑运算组合出来的。。 |
 |
29
susecjh 2019-01-18 07:56:06 +08:00 via Android
就这?
|
 |
30
YingJie 2019-01-18 08:43:56 +08:00 via Android
好像是 leetcode 简单级别的吧？
|
 |
31
northernlights 2019-01-18 10:04:05 +08:00
我想知道这样的动画演示是怎么制作出来的，谁能告诉我？
|
 |
32
smilev587 2019-01-18 10:46:15 +08:00
是我语文学的不好么？ 为啥后面你写的内容我都读不懂？
|
 |
33
jsp 2019-01-18 11:35:40 +08:00
其实位运算的各种性质都挺奇特的，很少回去留意。。 感谢楼主分享。
|
Select Language