这道题是真难. 我想了很久, 即使我一天都在外面转, 但脑子里一直在想.
可以再回顾一下 Single Number I, 那道题其实我想的很简单, 利用两个相同的数异或后为0的特点, 将全部数都依次异或, 结果剩下的就是我们要的 Single Number. 但其实这是利用了某种巧合. 不妨深入思考一下:
其实根据题意, 这个数字很特殊, 仅有两种状态:
- 重复一次的数
- 重复两次的数
只不过, 第一种情况只有一个数, 剩下的数全属于第二种情况. 而异或正好也表示了两种状态, 再结合一下上面咱们分析的状态:
- 不同的位 --> 1 --> 重复一次
- 相同的位 --> 0 --> 重复两次
虽然这里, 我们用的是 0 和 1 表示, 其实呢, 1 可以是任何 integer, 这里的bit, 只不过是对10进制运算的一种抽象. 所以上一道题的解法, 本质是借用异或运算, 表达了一个状态机, 0 -> 1 -> 0 -> ...
等等, 这像什么? 聪明, 就是二进制自加啊, 0x0 + 0x1 = 0x1; 0x1 + 0x1 = 0x0; 始终只有这两种状态. 本质是什么??? Yes! 二进制.
回到这道题, 重复两次的数变成了重复三次, 本质变了么? 没有, 我们需要的状态机是这个样子: 0 -> 1 -> 2 -> 0 -> ...
请问这是什么? 对了, 就是三进制. 我们要创造这样一种三进制, 让一个数出现三次后化为 0. 那么我们就可以仍旧依照上一道题的解法, 全加一遍即可.
二进制用 0, 1 一位表示足矣. 三进制呢? 就需要两位了吧, 是 (00, 01, 10) ==> (0, 1, 2). 以前是一位, 异或运算针对的也是一位, 这就是巧合. 现在就得需要靠自己创造了. 但还有一个特殊情况, 我们设计的两位, 应该屏蔽 11 这种组合. 这个在三进制中,其实应该等于 00.
好了, 用两个 int 表示这两个位:
int low = 0, high = 0;
低位先运算, 然后进位, 高低位分别异或. 即:
low = low ^ A[i];
high = high ^ A[i];但特殊条件也要考虑:
if (low == 1) high = 0. // 考虑 01 这种情况
if (high == 1) low = 0. // 考虑 10 这种情况这两句话极为啰嗦, low == 1 即 ~low = 0. 那么 high & ~low 也等于0. 所以可以将上面两段代码合为一段:
low ^= A[i] & ~high;
high ^= A[i] & ~low;OK, 这就是核心代码了, 放入循环遍历, 大功告成. AC.