欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客网剑指offer-数组中只出现一次的数字

程序员文章站 2022-03-08 15:49:40
...

题目描述

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。


class Solution {
public:
    //利用位运算的巧妙方法
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int sum = 0;
        //其他数都出现两次,异或之后抵消,最后只剩下出现一次的两个数的异或值
        for (int x : data)
            sum ^= x;
        //获得低位1,因为是异或结果所以也就是两个数最低的不同位
        int diff = sum&(-sum);
        *num1 = *num2 = 0;
        //根据不同位把数组分成两部分进行异或,最后分别剩下的数为答案
        for (int x : data)
        {
            if (x&diff)
                *num1 ^= x;
            else
                *num2 ^= x;
        }
    }
};