leetcode做题笔记137. 只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

思路一：位运算（参考ant大佬的思路）

c语言解法

int singleNumber(int* nums, int numsSize){
    int result = 0;
    for(int i=0;i<32;i++){
        long count =0;        
        for(int j=0;j
            count += (nums[j]>>i)&1;
        }
        result += (count%3)<
    }
    return result;
}

分析：

本题与上题相似，即要找出只出现了一次的元素，将每个数想象成32位的二进制，对于每一位的二进制的1和0累加起来必然是3N或者3N+1， 为3N代表目标值在这一位没贡献，3N+1代表目标值在这一位有贡献(=1)，然后将所有有贡献的位|起来就是结果。这样做的好处是如果题目改成K个一样，只需要把代码改成result%k，c语言解法要使用long才能将int类型左移31位，所以将count设置为long类型最后输出result

总结：

本题考察位运算对应找出单个数的普适性解法，可以利用位运算将每位数转换为各个数位上的记录，最后找出单个数，理解后可解决n个相同数，找单个数的问题