力扣第137题：只出现一次的数字 II C语言解法
力扣第137题：只出现一次的数字 II C语言解法标题描述
给定一个整数数组 nums，其中每个元素出现三次，除了一个元素出现一次。找出那个只出现一次的元素。
说明：
[*]你的算法应该具有线性时间复杂度。
[*]你不可以使用额外的空间（比方，哈希表）。
示例
示例 1:
输入: nums =
输出: 3
示例 2:
输入: nums =
输出: 99
提示
[*]1 <= nums.length <= 3 * 10^4
[*] − 2 31 ≤ n u m s [ i ] ≤ 2 31 − 1 -2^{31} \leq nums \leq 2^{31} - 1 −231≤nums≤231−1
[*]每个元素 nums 出现三次，除了某个元素只出现一次。
解题思路
1. 问题分析
[*]我们需要在一个包罗成百上千个元素的数组中，找出那个只出现一次的数字。数组中所有其他数字都出现了三次。
[*]这道题的关键是如何高效地找到那个只出现一次的元素，且需要在 O ( n ) O(n) 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; // twos 中保存的是同时出现在 ones 和 nums 中的位
ones ^= nums; // ones 中保存的是 nums 出现 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：
[*]更新 twos：twos |= ones & nums，将 ones 和当前数字的交集加入 twos。
[*]更新 ones：ones ^= nums，对当前数字进行异或操作，更新 ones。
[*]更新 threes：threes = ones & twos，表现同时出如今 ones 和 twos 中的位是出现了三次的位。
[*]从 ones 和 twos 中清除这些三次出现的位：ones &= ~threes 和 twos &= ~threes。
[*]终极，ones 中保存的就是只出现一次的数字。
5. 时间复杂度与空间复杂度
[*]时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是数组的长度。我们只需要遍历数组一次，且每次操作都是常数时间。
[*]空间复杂度： O ( 1 ) O(1) O(1)，我们只使用了常数级别的额外空间。
总结
这道题通过使用位运算的技巧（特殊是与、异或和位清除操作），我们可以或许高效地找出只出现一次的数字。相比于哈希表等通例方法，位运算不但能实现线性时间复杂度，而且可以或许节流空间，解决了标题中关于额外空间的限制。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]