问题出处：中文版 LeetCode 第 137 题 - 只出现一次的数字II 问题
问题描述：（源自 LeetCode）
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
解题思路：
以二进制数的角度考虑每一个数组元素，统计每一个二进制位上出现1的次数并对3取模（相当于：重复元素出现3次会被抵消清零），最终可以得到只出现一次的元素的二进制位情况，例如：对于 [ 9, 2, 2, 3, 2, 9, 9] 数组，其二进制位统计情况如表所示。
数字二进制位91001200102001070111200109100191001统计3144取模 % 30111
状态机：
对于统计部分进一步优化，使其每一位的统计值可以从0-2之间循环，即每当到达3时，自动变成0，为此，需要通过状态机机制来实现。
（1）由于循环范围为 0-2 之间，因此，需要两个二进制位来记录状态，如表所示。
状态值第二位（bit_2）第一位（bit_1）000101210
（2）列出不同状态下，对于不同输入值，对应的结果，如表所示。
原状态值原二位（ob2）原一位（ob1）输入值（input）新状态值新二位（nb2）新一位（nb1）000000010101012100210000110110112102101000注释：标红部分为计数增加的情况，由于取值范围为 0-2，因此，2 + 1 = 0。
（3）根据状态变化表，可以看出新二进制位为1的情况，对应的原二进制位值和输入值：
因此，可以得到状态值与输入值之间的关系表达式：
至此，已经可以按照该解决方案编写代码：
class Solution { public int singleNumber(int[] nums) { int b2 = 0, b1 = 0; // 初始化状态值 for (int input : nums) { // 遍历每一个输入值并计算 int temp = (~b2 & b1 & ~input) | (~b2 & ~b1 & input); b2 = (b2 & ~b1 & ~input) | (~b2 & b1 & input); b1 = temp; } return b1; // 最终状态值即为结果的二进制值 } }
（4）化简关系表达式：
通过观察，对于 nb1 的关系表达式，有公共项 ~ob2 可以提取，即 nb1 = ~ob2 & (ob1 & ~input | ~ob1 & input)
ob1 & ~input | ~ob1 & input 部分可以由异或来表达（二者不同，则为1），即 nb1 = ~ob2 & (ob1 ^ input)
将公式带入（2）中验证，可以验证该公式的正确性。
通过观察 ob2、nb1 和 input 与 nb2 的关系，可以得到新的表达式 nb2 = ob2 & ~nb1 & ~input | ~ob2 & ~nb1 & input
提取公共项 ~nb1 后得到 nb2 = ~nb1 & (ob2 & ~input | ~ob2 & input)，即 nb2 = ~nb1 & (ob2 ^ input)
因此，经过简化后的代码如下：
class Solution { public int singleNumber(int[] nums) { int b2 = 0, b1 = 0; // 初始化状态值 for (int input : nums) { // 遍历每一个输入值并计算 b1 = ~b2 & (b1 ^ input); // 此时 b1 为 nb1 b2 = ~b1 & (b2 ^ input); } return b1; // 最终状态值即为结果的二进制值 } }
相关文章
《全排列（Java）》
《位运算：减法与补码》
《异或（^）的性质与应用》
《图解：常用排序算法（冒泡、选择、插入、希尔、快速、归并、堆）》
《回溯算法（试探算法）》
《动态规划：鸡蛋掉落》
《动态规划：单词拆分》
《最小堆：TopK问题》
《链表：快慢指针》
