菜菜的简单题解

思路：这题思路是把数字拆分成位。int型是C++的内置类型，一般机器上为32位，本题中条件特殊每个数字都有出现k次，只有一个数字出现一次，自然想到对每位上的数字求和后%k，这样求余得到的数字就是我们所想要的。
复杂度分析：
时间复杂度O(n),空间复杂度O(1)

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param arr intvector
* @param k int
* @return int
*/

int foundOnceNumber(vector<int>& arr, int k) {
    // write code here
    int sum= 0;
    for(int i = 31;i>=0;i--){//int型32位，外层循环32次
        int cnt = 0;
        for(int j=0;j<arr.size();j++){
            cnt+=(arr[j]>>i)&1;//获得每个数字第i位的和O(n)
        }
        sum=2*sum+cnt%k;//其他数字都出现了k次，故余数是只出现一次的当前位，二进制转为十进制
    }
    return sum;
}

};