admin管理员组文章数量:1031225
【位运算】只出现一次的数字 II
137. 只出现一次的数字 II
137. 只出现一次的数字 II
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
示例 1：
代码语言：javascript代码运行次数：0运行复制输入：nums = [2,2,3,2]
输出：3示例 2：
代码语言：javascript代码运行次数：0运行复制输入：nums = [0,1,0,1,0,1,99]
输出：99提示：
1 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1nums中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
解题思路一：借用数组的位运算
原理很简单，一个数字每个比特位最大的数字就是 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 的倍数，则说明出现一次的数在该为也出现了，然后再将该为按位或到变量的该比特位上！
具体细节看代码：
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
int singleNumber(vector<int>& nums) {
int n = 0;
// 先遍历每一个数的每一比特位，看看一共出现多少次
for(int i = 0; i < 32; ++i)
{
int count = 0; // 用于统计该比特位出现了多少次1
for(int j = 0; j < nums.size(); ++j)
{
if((nums[j] >> i) & 1) // 只有该比特位出现1才处理
count++;
}
if(count % 3 != 0) // 如果出现了不是3的倍数，则说明出现一次的数在该为也出现了
n |= (1 << i);
}
return n;
}
};【位运算】只出现一次的数字 II
137. 只出现一次的数字 II
137. 只出现一次的数字 II
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
示例 1：
代码语言：javascript代码运行次数：0运行复制输入：nums = [2,2,3,2]
输出：3示例 2：
代码语言：javascript代码运行次数：0运行复制输入：nums = [0,1,0,1,0,1,99]
输出：99提示：
1 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1nums中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
解题思路一：借用数组的位运算
原理很简单，一个数字每个比特位最大的数字就是 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 的倍数，则说明出现一次的数在该为也出现了，然后再将该为按位或到变量的该比特位上！
具体细节看代码：
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
int singleNumber(vector<int>& nums) {
int n = 0;
// 先遍历每一个数的每一比特位，看看一共出现多少次
for(int i = 0; i < 32; ++i)
{
int count = 0; // 用于统计该比特位出现了多少次1
for(int j = 0; j < nums.size(); ++j)
{
if((nums[j] >> i) & 1) // 只有该比特位出现1才处理
count++;
}
if(count % 3 != 0) // 如果出现了不是3的倍数，则说明出现一次的数在该为也出现了
n |= (1 << i);
}
return n;
}
};本文标签： 位运算只出现一次的数字 II
版权声明：本文标题：【位运算】只出现一次的数字 II 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1747718406a2208359.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论