《剑指 Offer》专项突破版 - 面试题 4 : 只出现一次的数字（C++ 实现）

题目链接：137. 只出现一次的数字 II - 力扣（LeetCode）

题目：

输入一个整数数组，数组中只有一个数字出现了一次，而其他数字都出现了 3 次。请找出那个只出现一次的数字。例如，如果输入的数组为 [0, 1, 0, 1, 0, 1, 100]，则只出现一次的数字是 100。

分析：

这个题目有一个简化版的类似的题目 "输入数组中除了一个数字只出现一次之外其他数字都出现两次，请找出只出现一次的数字"。任何一个数字异或它自己的结果都是 0，即 x ^ x = 0。如果将数组中所有数字进行异或运算，那么最终的结果就是那个只出现一次的数字。

class Solution {
public:
 ? ?int singleNumber(vector<int>& nums) {
 ? ? ? ?int result = nums[0];
 ? ? ? ?for (int i = 1; i < nums.size(); ++i)
 ? ? ?  {
 ? ? ? ? ? ?result ^= nums[i];
 ? ? ?  }
 ? ? ? ?return result;
 ?  }
};

在这个题目中只有一个数字出现了一次，其他数字出现了 3 次。相同的 3 个数字异或的结果是数字本身，即 x ^ x ^ x = x，因此将数组中所有数字进行异或运算并不能消除 3 次的数字，需要想其他办法。

一个整数是由 32 个 0 或 1 组成的。我们可以将数组中所有数字的同一位置的数位相加。

1. 如果数组中所有数字的第 i 个数位相加之和能被 3 整除，那么只出现一次的数字的第 i 个数位一定是 0。

   sum 为 0 或 3k（k > 0）。

2. 如果数组中所有数字的第 i 个数位相加之和被 3 除余 1，那么只出现一次的数字的第 i 个数位一定是 1。

   sum 为 1 或 1 + 3k（k > 0）。

代码实现：

class Solution {
public:
 ? ?int singleNumber(vector<int>& nums) {
 ? ? ? ?int result = 0;
 ? ? ? ?for (int i = 0; i < 32; ++i)
 ? ? ?  {
 ? ? ? ? ? ?int sum = 0;
 ? ? ? ? ? ?for (int j = 0; j < nums.size(); ++j)
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?if (nums[j] & (1 << i))
 ? ? ? ? ? ? ? ? ? ?++sum;
 ? ? ? ? ?  }
?
 ? ? ? ? ? ?if (sum % 3 == 1)
 ? ? ? ? ? ? ? ?result |= 1 << i;
 ? ? ?  }
 ? ? ? ?return result;
 ?  }
};

举一反三：

题目：

输入一个整数数组，数组中只有一个数字出现 m 次，其他数字都出现 n 次，请找出那个唯一出现 m 次的数字。假设 m 不能被 n 整除。

分析：

如果数组中所有数字的第 i 个数位相加之和能被 n 整除，那么出现 m 次的数字的第 i 个数位一定是 0；否则出现 m 次的数字的第 i 个数位一定是 1。