力扣第137题：只出现一次的数字 II C语言解法
标题描述
给定一个整数数组 nums，其中每个元素出现三次，除了一个元素出现一次。找出那个只出现一次的元素。
说明：
- 你的算法应该具有线性时间复杂度。
- 你不可以使用额外的空间（比方，哈希表）。
示例
示例 1:
- 输入: nums = [2,2,3,2]
- 输出: 3
- 输入: nums = [0,1,0,1,0,1,99]
- 输出: 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[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：
- 更新 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企服之家，中国第一个企服评测及商务社交产业平台。 |
