当前位置：首页 > news >正文

【位运算】只出现一次的数字 II

news 来源：原创 2025/9/11 9:31:52

文章目录

137. 只出现一次的数字 II
解题思路一：借用数组的位运算
解法二：不使用数组的位运算

137. 只出现一次的数字 II

137. 只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现 **三次。**请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现一次外，其余每个元素都恰出现三次

解题思路一：借用数组的位运算

原理很简单，一个数字每个比特位最大的数字就是 1，那么我们把每个数字的每一比特位累加到数组中对应的下标元素处，然后判断这些元素中，哪些是 3 的整数倍的，如果是 3 的整数倍的话，说明就是出现了 3 次的元素，而如果不是的话，说明那个出现了一次的元素的比特位在该位置上也出现过，所以我们就用一个变量记录下这个位，以此循环，最后得到的就是那个出现一次的元素！

在这里插入图片描述

class Solution {
public:int singleNumber(vector<int>& nums) {int hash[32] = { 0 };// 将每个数字的每一比特位都累加到n的每一比特位上for(int i = 0; i < nums.size(); ++i){for(int j = 0; j < 32; ++j){if((nums[i] >> j) & 1)hash[j]++;}}// 将hash中模3不为0的比特位设置到ret对应位置int ret = 0;for(int i = 0; i < 32; ++i){if(hash[i] % 3 != 0)ret |= (1 << i);}return ret;}
};

解法二：不使用数组的位运算

上面这种做法虽然时间复杂度是 O(n)，但是空间复杂度也是 O(n)，其实我们可以 直接用一个变量，通过位运算来达到同样的效果，还能做到节省空间！

和上面的题解不太一样的是，因为我们使用的是一个变量，那么该变量每个比特位最多也就是 1，不能拿来累加多次，所以我们 必须先判断每个数的每一位出现了多少次，遍历完所有数的一个比特位之后，如果该位出现了不是 3 的倍数，则说明出现一次的数在该为也出现了，然后再将该为按位或到变量的该比特位上！

具体细节看代码：

class Solution {
public:int singleNumber(vector<int>& nums) {int n = 0;// 先遍历每一个数的每一比特位，看看一共出现多少次for(int i = 0; i < 32; ++i){int count = 0; // 用于统计该比特位出现了多少次1for(int j = 0; j < nums.size(); ++j){if((nums[j] >> i) & 1) // 只有该比特位出现1才处理count++;}if(count % 3 != 0) // 如果出现了不是3的倍数，则说明出现一次的数在该为也出现了n |= (1 << i);}return n;}
};

在这里插入图片描述

文章目录

137. 只出现一次的数字 II

解题思路一：借用数组的位运算

解法二：不使用数组的位运算

相关文章：