算法:找出只出现一次的数

所有的数都出现两遍,只有一个数出现一遍,找出这个数来。或者描述成,所有的用户都有登入和登出操作,只有一个用户没有登出,找出这个用户ID来。这个问题很简单,只需要全部异或一遍即可。

略微升级版问题为:一个数组中,所有数都出现两遍,只有两个数出现一遍,找出这两个数。也是用异或,不过需要描述两遍了。其实核心就是,当某一位的异或结果为1时,表示有奇数个1相异或,为0,即表示有偶数个1相异或。代码如下:

int arr[] = {1,9,199,101,9,76,123,199,1,101,88,123};

int main(int argc, char *argv[])
{
    int len = sizeof(arr)/sizeof(int);
    int res = 0;
    for (int i=0; i<len; ++i) {
        res ^= arr[i];
    }
    int tmp = 1;
    while (true) {
        if (tmp & res) {
            res = tmp;
            break;
        }
        tmp <<= 1;
    }
    int a = 0;
    int b = 0;
    for (int i=0; i<len; ++i) {
        if (res & arr[i]) {
            a ^= arr[i];
        } else {
            b ^= arr[i];
        }
    }
    cout<<a<<" "<<b<<endl;
    return 0;
}

 

发表于2018-06-23 11:21   修改于2018-06-23 11:21   评论:0   阅读:149  



回到顶部

首页 | 关于我 | 关于本站 | 站内留言 | rss
python logo   django logo