Problem

Given a non-empty 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

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

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

Code

static int var = [](){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end(),less<int>());
        int i = 0;
        while(i<nums.size()-1&&nums[i]==nums[i+1]){
            i+=2;
        }
        return nums[i];
    }
};

Result

136. Single Number.png