剑指Offer-面试题56-II：数组中唯一只出现一次的数字 位运算

这里是题目描述：剑指Offer-面试题56-II：数组中唯一只出现一次的数字

本题可以用哈希表统计数组中每个数字出现次数，时间复杂度O(n)，空间复杂度O(n)。我们可以使用位运算的方法，将空间复杂度降至O(1)——统计数组中所有数字在二进制各个位上为1的次数总和：

因为数组中出现次数不为1的数字都出现了3次，所以某一数字二进制上某一位为1的时候，这一位一定会出现3次为1。因此除去只出现一次的数字，数组中其他数字在二进制各个位上1出现的次数可以被3整除。再加上只出现一次数字在二进制上的1，那么某一位上的和能被3整除，该位在只出现一次数字中为0；如果被3除后余1，该位在只出现一次数字中为1

示例

输入：nums=[3,4,3,3]
3 的二进制：011
4 的二进制：100
nums中各个位为1的总和：133
各个位%3后：100 --> 4

题解代码：

class Solution {
public int singleNumber(int[] nums) {
if(nums.length==1)
{
return nums[0];
}
int[] bitCount=new int[32]; //统计int类型的nums[]的所有元素的某一二进制位为1的个数
for(int i=0;i<nums.length;i++)
{
int t=1;
for(int j=0;j<32;j++)
{
if((nums[i]&t)!=0) //该位不为0
{
bitCount[j]+=1;
}
t=t<<1;
}
}
int res=0;
for(int i=bitCount.length-1;i>=0;i--)
{
res=res*2+bitCount[i]%3; //bitCount[i]%3的结果就是唯一数字在二进制第i位的状态（0或1）
}
return res;
}
}

时间复杂度：每个nums中的元素需要在32位上做加法，然后还需要对结果的每一位%3，然后用32位取余结果重构只出现一次的数字，因此需要32*n+32+32次运算，时间复杂度为O(n)

空间复杂度：只需要一个固定程度为32的数组统计各个位上1出现的次数，空间复杂度为O(1)

最后

以上就是细心小笼包为你收集整理的剑指Offer-面试题56-II：数组中唯一只出现一次的数字 位运算的全部内容，希望文章能够帮你解决剑指Offer-面试题56-II：数组中唯一只出现一次的数字 位运算所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。