LeetCode No.136

只出现一次的数字

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入：[2,2,1] 输出：1

示例 2:

输入：[4,1,2,1,2] 输出：4

算法思想

老规矩找到问题给出的性质——目标元素只出现一次，剩余元素出现两次。

不多不少，正好两次。显然这是一个主要的突破口。

两次很容易让我们想到，假如非目标元素两两揍一顿互相抵消就好了。什么方式可以让相同的数抵消，不同的数保留呢？

数位的异或运算

位的角度来看：1^1=0 0^0=0 1⁰⁼⁰1=1

即相同的位会清空，不相同的位会保留。

并且多位运算时：1¹0=1⁽¹0)=(1⁰⁾1=0

易知位的异或运算具有结合律和交换律——即运算顺序不影响运算结果

数的异或

从数位异或中可以看出，偶数次的 1 或者 0 运算后都是 0，在数的层面上也是一样，出现偶数次的数两两运算后也为 0。而 0 和任何数异或等于数本身。

因此对整个数组进行异或运算，相当于最后剩个 0 和目标元素异或，结果就是目标值。

题解代码

class Solution {
public:
    int singleNumber(vector<int& nums)
    {
        //异或运算 相同的数异或归 0 且异或具有交换律
        int result=0;
        for (auto num :nums)
        {
            result^=num;
        }

        return result;
    }
};