首页 > itarticle > 位操作算法一

位操作算法一

admin 11月 12, 2020 0

参考出处
长度为n的数组包含k个数字（n=3×k+1)，其中k-1个数字出现了3次，一个数字出现了一次，求这个数字是多少（要求时间复杂度为O(n)，空间复杂度为O(1)）
数每位1的个数除以3得到结果


using namespace std;
int ()
{ 
    int n, res = 0;
    cin>>n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin>>a[i];
    
    for(int i = 0; i < 32; i++){
        int x = (1<<i);
        int sum = 0;
        for(int j = 0; j < n; j++){
            if(a[j]&x) sum++;
        }
        if(sum%3) res += x;
    }
    cout<<res<<endl;
    return 0;
}

当然也可以通过集合来解决此问题.(3*(去重之后的集合) - (原集合之和))/2 == ans.