[LeetCode][136][260] Single Number I and III

作者 Shilei Tian 日期 2016-04-19
[LeetCode][136][260] Single Number I and III

这是 LeetCode 上两道 Medium 级别的题,属于同一个系列,该系列一共三道题,还有 II 没有做,等做了再补充。先看下第一题的要求:

Given an array of integers, every element appears twice except for one. Find that single one.

第一题说有一个数组,里面除一个元素只出现一次外,其余的元素都出现两次,让找到这个单个元素。这道题解法很多,线性时间的解法中,我们提出位运算的思想,该思想在 III 中也会用到。

大家都知道,逻辑运算异或 a⊕b=(¬a∧b)∨(a∧¬b),用中文解释一下,就是如果 a=b,那么 a⊕b=0,否则 a⊕b=1。还有一个重要的性质,就是 a⊕0=a,这两道题就用到了这个性质。考虑第一题,既然其余的元素都出现过两次,那么把这些元素进行异或操作后,结果必然为 0,再结合重要性质,用剩下的那个元素异或 0 则会得到那个元素本身,因此我们可以直接扫一遍数组,让他们之间进行一次异或,最后就可以得到想要的元素。代码如下:

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (auto num : nums) {
ret ^= num;
}
return ret;
}
};

上面这道题很简单,接下来我们看 III 的要求:

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. For example: Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

说呀,有这么一个数组,这些元素只有两个元素只出现一次,其余的元素还是出现两次,与第一次不同的地方在于,这一题中出现一次的元素变成两个了,它还给出了一个例子。那我们是不是还可以继续用位运算来做呢?答案是肯定的。那这次对所有的元素进行异或操作后会得到什么呢?会得到那两个单独的元素异或后的结果,比如拿它给的例子来说,最终会得到 3⊕5=6。题目的要求是返回这两个元素,那么我们如何做才能分开它们得到信息呢?如果能够让他们分成两组,每一组里面只有一个单个出现的元素,然后它们之间进行异或操作,不就得到两个单个元素了吗,这样该多好呀!那么,下面这个小技巧就是来实现这个目标的。

我们先看一下异或操作的实质:对于两个数的每一位,如果这两位相同,那么这两位异或的结果就是 0,否则就是 1。那么我们可以想到,异或得到的结果从低位向高位看,第一个 1 出现的那一位,就是这两个二进制数第一位出现不相等的地方,那么它们两个肯定有一个数这一位是 1,另一个数这一位是 0。因此,我们就可以根据这个,将数组里面的元素分成两组:一组是每一个元素这一位都是 0,另一组是每一个元素这一位都是 1。这样,我们不就得到了想要的两个分组,每一个分组只有一个单个元素,其他的元素势必成对存在。

有了上面的理论,下面就需要考虑,那如何求得这一位呢?这个技巧就是:xor &= -xor!为什么这样做呢?大家可以动手画一画二进制数字,如何做才能获得那一位。不信大家可以动手试试,对于任何元素,它与它的相反数进行逻辑与后,得到的值就是该数对应二进制位从低位向高位数第一个出现 1 的那一位对应的数字。5 & -5 = 1

好了,所有的理论讲完了,下面就看看代码了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int diff = accumulate(nums.rbegin(), nums.rend(), 0, bit_xor<int>());
diff &= -diff;
vector<int> ret = {0, 0};
for (auto num : nums) {
if ((num & diff) == 0) {
ret[0] ^= num;
} else {
ret[1] ^= num;
}
}
return ret;
}
};

代码的第 4 行是用到了只读泛型算法 accumulate,你可以在这里看到它。这里为什么用反向迭代器呢?《C++ Primer 5th Edition》中 9.3.2 节提到:

When write access is not needed, use cbegin and cend.

还剩下一个第 II 题,暂时还没做,做完了补充。