力扣第137题：只出现一次的数字 II C语言解法

题目描述

给定一个整数数组 nums，其中每个元素出现三次，除了一个元素出现一次。找出那个只出现一次的元素。

说明：

你的算法应该具有线性时间复杂度。
你不可以使用额外的空间（例如，哈希表）。

示例

示例 1:

输入: nums = [2,2,3,2]
输出: 3

示例 2:

输入: nums = [0,1,0,1,0,1,99]
输出: 99

提示

1 <= nums.length <= 3 * 10^4
$-2^{31} \leq nums[i] \leq 2^{31} - 1$
每个元素 nums[i] 出现三次，除了某个元素只出现一次。

解题思路

1. 问题分析

我们需要在一个包含成百上千个元素的数组中，找出那个只出现一次的数字。数组中所有其他数字都出现了三次。
这道题的关键是如何高效地找到那个只出现一次的元素，且需要在 $O (n)$ 的时间复杂度内完成。

2. 位运算的妙用

与运算：与运算可以帮助我们判断数字的各个位是否相同。例如，1 & 1 = 1，1 & 0 = 0，0 & 0 = 0。
异或运算：异或运算具有自反性，x ^ x = 0 和 x ^ 0 = x，可以帮助我们消去出现两次的数字。
位运算的思路：
- 如果每个数字出现三次，那么每一位（例如：第 0 位、第 1 位、…）的数字出现的次数也应该是 3 的倍数（或者 3n 次）。
- 但是，数字中只出现一次的那个元素，在其各个位上的数字出现的次数就会是 1。
- 我们可以通过按位统计来找出那个出现一次的数字。

3. 具体思路

我们可以使用 3 个整数变量来辅助解决问题。我们通过位运算的方法来分析每一位的出现次数，最终得到只出现一次的元素。
使用 3 个变量：
- ones: 存储当前数字在某个位上出现次数为 1 的结果。
- twos: 存储当前数字在某个位上出现次数为 2 的结果。
- threes: 存储当前数字在某个位上出现次数为 3 的结果。

关键操作：

对于每个数字，我们要更新 ones 和 twos。
如果某个位上的数字出现了 3 次，那么就把该位上的数字从 ones 和 twos 中去除。
最终，ones 中保存的就是只出现一次的数字。

4. 算法实现

我们对每个数字进行逐位处理，更新 ones 和 twos，直到找到那个只出现一次的数字。

C语言代码实现

#include <stdio.h>

int singleNumber(int* nums, int numsSize) {
    int ones = 0, twos = 0, threes = 0;
    
    for (int i = 0; i < numsSize; i++) {
        twos |= ones & nums[i]; // twos 中保存的是同时出现在 ones 和 nums[i] 中的位
        ones ^= nums[i];        // ones 中保存的是 nums[i] 出现 1 次的位
        
        threes = ones & twos;   // threes 保存的是在 ones 和 twos 中都出现的位
        ones &= ~threes;        // 如果某一位在 ones 和 twos 中都出现过 3 次，则从 ones 中清除
        twos &= ~threes;        // 同样，从 twos 中清除
    }
    
    return ones;  // 最终返回只出现一次的数字
}

int main() {
    int nums1[] = {2, 2, 3, 2};
    int nums2[] = {0, 1, 0, 1, 0, 1, 99};
    
    printf("Result 1: %d\n", singleNumber(nums1, 4));  // 输出 3
    printf("Result 2: %d\n", singleNumber(nums2, 7));  // 输出 99
    
    return 0;
}

代码解释

变量说明：
- ones：保存当前数字在各个位上出现次数为 1 的结果。
- twos：保存当前数字在各个位上出现次数为 2 的结果。
- threes：保存当前数字在各个位上出现次数为 3 的结果。
算法步骤：
- 对于每个数字 nums[i]：
  - 更新 twos：twos |= ones & nums[i]，将 ones 和当前数字的交集加入 twos。
  - 更新 ones：ones ^= nums[i]，对当前数字进行异或操作，更新 ones。
  - 更新 threes：threes = ones & twos，表示同时出现在 ones 和 twos 中的位是出现了三次的位。
  - 从 ones 和 twos 中清除这些三次出现的位：ones &= ~threes 和 twos &= ~threes。
- 最终，ones 中保存的就是只出现一次的数字。