剑指offer专项突破版(4)—— 只出现一次的数字_亚洲第一中锋_哈达迪的博客-爱代码爱编程
题目
思路
本题需要用二进制的思路来看。一个整数由32位组成。我们可以将数组中所有数字的同一位置的数位相加,数组中除了那个只出现一次的数以外,其他的数相加的结果中,每一位一定是3的倍数(因为都出现3次嘛)
然后我们把只出现一次的数A
加进去,看每一个二进制位i
:
i % 3 == 0
:A的二进制形式在这一位是0
i % 3 == 1
:A的二进制形式在这一位是1
因此我们可以根据A
在每一位是0还是1,最终将A拼出来
代码
public int singleNumber(int[] nums) {
int[] arr = new int[32];
for (int num : nums) {
for (int i = 0;i<32;i++) {
// 提取num的第i位,加到arr[i]中
arr[i] += (num >> i) & 1;
}
}
int res = 0;
for (int i = 0;i<32;i++) {
// 根据第i位 % 3的结果是0还是1,将结果拼到res
res |= (arr[i] % 3 == 0 ? 0 : 1) << i;
}
return res;
}