leetcode 136. Numbers that appear only once (XOR!!)

Given a non-empty array of integers, each element appears twice except one that appears only once.Find the element that appears only once.

Description:

Your algorithm should have linear time complexity.Can you do it without using extra space?

Example 1:

Input: [2,2,1]
Output: 1
Example 2:

Input: [4,1,2,1,2]
Output: 4

Ideas: Use XOR

The XOR operation has the following three properties:

1. If any number is XORed with 0, the result is still the original number, i.e. a^0=a .
2. Any number is XORed with itself, the result is 0, that is, a^a=0.
3. The XOR operation satisfies the commutative and associative laws, that is, a ^ b ^ a=b ^ a ^ a=b ^ (a ^ a)=b ^ 0=b .

At the beginning, let int ans=0, traverse the entire array and perform an XOR operation. Since the elements that appear 2 times are XORed 2 times, they are still themselves, and finally only the elements that have XORed 1 times are left, and because 0XOR with any number is that number itself, so in the end only one occurrence of the number is left.

class Solution {public:int singleNumber(vector<int>& nums) {int ans=0;int n=nums.size();for(int i=0;i<n;++i)ans^=nums[i];return ans;}};