⭐ 题目日期：

美团 - 2024/9/4

🌳 题目描述：

一个数组，其中一个数字出现一次，其余出现两次，找出只出现一次的数字。

🌟 追问:

一个数组，其中一个数字出现一次，其余出现 K 次(K为大于 1 的奇数)，找出只出现一次的数字。

要求：时间复杂度O(n), 空间复杂度 O(1)

🕵🏽 面试评估：

这道题考查位运算的基本功，各种位运算的理解与熟练使用，位运算是一个在面试准备中容易忽略的方向，这道题也提醒我们平时的准备需要兼顾算法的深度与广度。

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

在访问第 i 个数时，在不借助额外数据结构存储已访问的元素的情况下，我们无法判断当前访问的数有没有出现过。

那我们有没有方法通过某种运算让出现两次的数消失，最终的运算结果就是只出现一次的数。而位运算中的异或(XOR, 在Java中，用'^'表示) 可以。异或运算规则为：相同为 0，不同为 1。0 ^ 0 = 0; 1 ^ 1 = 0; 1 ^ 0 = 1;

让数组中的所有数异或，直接找到答案。

追问：一个数组，其中一个数字出现一次，其余出现 K 次(K为大于 1 的奇数)，找出只出现一次的数字。

相同的数奇数次异或，得到数本身。举例：数字 2 异或 3 次， 数字 2 二进制表示为 10, 10 ^ 10 = 0, 0^10 = 10

所以，我们无法用第一题的方法求解。

既然无法将所有数的二进制位进行异或运算，那能否做其他的运算？比如说“加法运算”，统计数组中所有的数在某个二进制位出现的次数，如果有二进制位出现的次数不是K的整数倍，说明有其他没有出现K次的数的贡献，而该数只有一个，就是答案。

💻代码：

Java

 public int singleNumber(int[] nums) {
     int result = 0;
     for (int num : nums) {
         result ^= num;
     }

     return result;
 }

其余出现 k 次代码：

Java

 public int singleNumber(int[] nums, int k) {
     int result = 0;
     // 整数由32位二进制表示
     int numDigits = 32;

     for (int i = 0; i < numDigits; i++) {
         int count = 0;
         for (int j = 0; j < nums.length; j++) {
             // 统计数组中所有元素，从右向左数第 i 位二进制位上 1 的个数，>> 为右移操作
             count += (nums[j] >> i & 1);
         }
         if (count % k == 1) {
             // 还原只出现一次的数 1 的分布，<< 为左移操作
             result |= (1 << i);
         }
     }

     return result;
 }

🚵🏻复杂度分析：

时间复杂度: O(n)

空间复杂度: O(1)