安卓原生开发_成都一日游攻略_济源网络推广_seo案例分析

处理这种数据集中只有一个数出现的频次为1，其他数出现的频次均为k的题目

往往都是使用位运算的进行求解

假设 target在数据集中只出现了1次，其他数据n1, ... nj都出现了 k 次，

考虑数据集中所有数据的第 i 位的取值，那么将会有j + 1个比特位，其中如果n1 到 nj中有且仅有 x个数字在第 i 位取1，其他的数字在第 i 位取0

那么将这 j 个数全部相加，得到的结果为α，α一定是 k 的倍数，

那么((target >> i ) & 1 + α) % k一定等于(target >> i ) & 1

所以将这j + 1个比特位相加之后对k 取模，得到的一定是 target在第 k位的取值

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i < 32; i++){int tmp = 0;for(auto & num : nums){tmp += (num >> i) & 1;}ret += ((tmp % 3) << i);}return ret;}
};