只出现一次的数2 🌟🌟🌟中等
课后作业
问题描述
原文链接：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 - 1nums中，除某个元素仅出现一次外，其余每个元素都恰出现三次
代码实现
Java
class Solution {
public int singleNumber(int[] nums) {
int[] res = new int[32];
int m = 1;
int sum = 0;
for(int i = 0; i < 32; i++){
for(int j = 0; j < nums.length; j++){
if((nums[j] & m) != 0){
res[i]++;
}
}
res[i] = res[i] % 3;
sum = sum + res[i] * m;
m = m << 1;
}
return sum;
}
}
Python
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = [0] * 32
m = 1
sum = 0
for i in range(32):
for j in range(len(nums)):
if (nums[j] & m) != 0:
res[i] += 1
res[i] = res[i] % 3
sum += res[i] * m
m = m << 1
# 将结果转换为有符号整数
if res[31] == 1:
sum = -(2 ** 32 - sum)
return sum
C++
class Solution {
public:
int singleNumber(vector<int>& nums) {
vector<int> res(32);
unsigned int m = 1;
int sum = 0;
for(int i = 0; i < 32; i++){
for(int j = 0; j < nums.size(); j++){
if((nums[j] & m) != 0){
res[i]++;
}
}
res[i] = res[i] % 3;
sum = sum + res[i] * m;
m = m << 1;
}
return sum;
}
};
Go
func singleNumber(nums []int) int {
ones, twos := 0, 0
for _, num := range nums {
ones = (ones ^ num) & (^twos)
twos = (twos ^ num) & (^ones)
}
return ones
}