[Q137]只出现一次的数字 Ⅱ
[Q137]只出现一次的数字 Ⅱ
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1：
-
输入：nums = [2,2,3,2] 输出：3
示例 2：
-
输入：nums = [0,1,0,1,0,1,99] 输出：99
思路
数组中元素为int类型，有32位二进制位。 对于数组中[非答案]的元素，每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个 0 或 3 个 1，无论是哪一种情况，它们的和都是 3 的倍数。
若这个[只出现一次的数字]的第i位二进制位为1，则第i位二进制位的和为3的倍数+1（即不为3的倍数）,那么将答案的第i位二进制位置1。
Java代码实现
class Solution {
public int singleNumber(int[] nums) {
int answer = 0;
for(int i = 0; i < 32; i++){
int total = 0;
for(int num:nums){
total += (num >> i) & 1;
}
if(total % 3 != 0){
answer |= (1 << i);
}
}
return answer;
}
}
复杂度分析
-
时间复杂度：O(n log C)。 空间复杂度：O(1)。
下一篇：
[牛客算法总结]：重建二叉树