2019-06-02 15:09:36
Single Number 问题其实我很早就遇到了，当时还是第一次刷leetcode，那个时候完全没有想到怎么在<O(n), O(1)>完成这个解答，看了答案之后才恍然大悟，原来可以使用异或来解决。这个问题还有很多的变种问题，比如1-n的数字缺少了一个，找到缺失的那一个(补齐1 - n, 就变成了Single Number)，等等。
后来接触题目渐多之后，发现原来Single Number只是一个特例，这个问题可扩展性非常强。
一、Single Number
问题描述：
问题求解：
经典的使用异或解决的问题。
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) res ^= num;
return res;
}
二、Single Number II
问题描述：
问题求解：
结合Single Number，SN问题本质上是由于对于异或操作来说，每一位置上如果出现了两个1，那么就会归零。考虑到这个问题，如果我们能定义一个“异或操作”，对于每个位出现3次1就归零就好了。那么，显然的对于每一个位仅仅采用原生的01就不够了，我们需要至少两位才能表征0，1， 2， 3这三个状态。
真值表如下：
根据真值表，我们很容易就能推算出a,b的递推公式：
a = a!b!c + !abc
b = !ab!c + !a!bc
显然的是ab == 00代表的是0，ab中任意一位为1的时候代表的是1，那么最后的结果就是a | b。
public int singleNumber(int[] nums) {
int a = 0;
int b = 0;
for (int c : nums) {
int _a = a;
a = (a & ~b & ~c) | (~a & b & c);
b = (~_a & b & ~c) | (~_a & ~b & c);
}
return a | b;
}