Single Number

LeetCode #136

Description:

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example:

Note

Idea:

0^x==x
x^x==0

这个XOR方法也可以用于swap integers。

Code:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result=0;
        for(auto e: nums){
            result ^= e;
        }
        return result;
    }
};