一、问题描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
题目链接：只出现一次的数字
二、题目要求
样例 1
输入: [2,2,1] 输出: 1
样例 2
输入: [4,1,2,1,2] 输出: 4
考察
位运算异或、双指针、数学思想 建议用时15~30min
三、问题分析
本题是位运算的第1题，没了解过位运算相关知识点可以看这一篇文章：
1.双指针
一开始，我想的是先对数组从小到大排序。举两个例子，排序后如下：
112241233两两对比，因为排序后相等的数字都会聚集到一起，假如不相等就输出，OK！
classSolution { public: intsingleNumber(vector<int>&nums) { inti=0,j=1,n=nums.size();//双指针i jsort(nums.begin(),nums.end());//排序while(i<n&&j<n) { if(nums[i]!=nums[j])//不相等 { returnnums[i];//直接返回结果 } i+=2,j+=2;//向后顺延两个 } returnnums[n-1];//输出最后一个 } };
2.位运算
位运算一开始属实没想到，看了题解之后发现解法十分巧妙。
异或就是相同的两个数字会被消掉，异或运算满足交换律和结合律，比如：
4^1^2^1^2 = 1^1^2^2^4 = 0^0^4 = 4
结果就是最后一个没有被消掉的数字。
四、编码实现
classSolution { public: intsingleNumber(vector<int>&nums) { inti=0,n=nums.size();//初始化for(i=1;i<n;i++) { nums[i]=nums[i]^nums[i-1];//异或开始 } returnnums[n-1];//输出结果};
