C++利用“异或”

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

看到了一个很有意思的解法

  int singleNumber(vector<int> &nums)
{
    int a = 0;
    for (int i : nums)
    {
        a ^= i;
    }
    return a;
}

这个题要想漂亮的解决,首先就要了解“异或”特点

  1. 异或可以用来交换两个变量的值,不用申请空间。
int a=5,b=7;
a=a^b;
b=a^b;
a=a^b;
//a=7,b=5

2.两个相同的值进行异或后为0,0与A异或结果为A

int a=7,b=7,c=0;
a^b    //0
a^c    //7

3.异或满足交换律

a^b^c=a^c^b

分析

这道题可利用异或的第2和第3个性质,先设定一个初始值a=0,假定这个数列为{A,B,A},他的算法是将a与每一个数异或,a与A异或后,a=A,之后与B异或,但由于异或满足交换,可以等价于先于第二个A异或,这样根据第二个性质,a=0,a再次与B异或时,a=B,但因为B只有一个,所以就找到了这个唯一的值。


发表评论