LeetCode136：只出现一次的数字

 题目

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

说明：

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

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

这是《数据结构基础》中的第一道题，主要思想是位运算中异或运算，可参考以下：

1. 任何数于0异或为任何数 0 ^ n => n

2. 相同的数异或为0: n ^ n => 0

例如：2 ^ 3 ^ 2 ^ 4 ^ 4等价于 2 ^ 2 ^ 4 ^ 4 ^ 3 => 0 ^ 0 ^3 => 3

故对于本题，想找到只出现一次的元素，只需要将数组中的每个数进行异或运算，出现两次的数异或为0（n ^ n => 0），最后只剩下只出现一次的数（0 ^ n => n）。

实现

本题，个人采用C++实现，原理弄清楚后，还需要了解异或函数【bit_xor()】的使用。具体使用示例整理如下：

 #include <algorithm> 
 #include <functional> // to include bit_xor 
 #include <iostream> 
 #include <iterator> 
 using namespace std; 
   
 int main() 
 { 
     // declaring the values 
     int A[] = { 1, 2, 3, 4, 5, 6 }; 
     int B[] = { 6, 7, 8, 4, 5, 0 }; 
     int n = 6; 
     // defining result 
     int result[n]; 
   
     // transform is used to apply bitwise_xor 
     // on the arguments A and B 
     transform(A, end(A), B, 
               result, bit_xor<int>()); 
   
     // printing the resulting array 
     cout << "A xor B = "; 
     for (const int& answer:result) 
         cout << ' ' << answer; 
   
     return 0; 
 } 

上述例子是对于两个数组进行异或，事实上，针对本题对一个数组中所有数进行异或，可以写成

accumulate(nums.begin(),nums.end(),0,bit_xor());

 综上，可以得出以下代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a=0;
        for(int i=0;i<sizeof(nums);i++)
        {
            a=accumulate(nums.begin(),nums.end(),0,bit_xor());
        }
        return a;
    }
};