查找出现奇数次的数(2)

一个数组中有两种数出现了奇数次,其他数都出现了偶数次,怎么找到这两个数
思路:
分两组,每组都只有一种奇数个数的数
void GetOdd(int arr[], int len, int ans[]) { //数组 ans 储存结果
    int eor = 0;

    for(int i = 0; i < len; ++i) eor ^= arr[i];

    int ano = 0; //储存其中一个结果

    int temp = eor & (~eor + 1); //保留 eor 最右边的 1 ,其他位全置为 0 赋值给 temp

    for(int i = 0; i < len; ++i) { //以 temp 分组将其中一组异或给 ano
        if((arr[i] & temp) != temp) ano ^= arr[i]; 
    }

    eor ^= ano; //eor 异或 ano 得到另一种数

    ans[0] = eor; //赋值
    ans[1] = ano;
}
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务