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?

这道题首先由于不开辟其他内存，所以想到了先排序再寻找，首先是冒泡排序：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int min, max;
        //冒泡排序
        for(int i = 0; i< nums.size(); i++){
            for(int j = i; j<nums.size()-i; j++){
                if(nums[j] < nums[i]){
                    swap(nums[i], nums[j]);
                }else if(nums[j] > nums[nums.size()-i-1]){
                    swap(nums[j], nums[nums.size()-i-1]);
                }
            }
        }
        //在已经排好序的数组中进行寻找
        for(int i = 0; i < nums.size(); i+=2){
            if(i == 0&&nums[0]!=nums[1]){
                return nums[0];
                break;
            }else if(i == nums.size()-1&&nums[i]!= nums[i-1]){
                return nums[nums.size()-1];
                break;
            }
            else if(nums[i]!=nums[i+1]){
                return nums[i];
                break;
            }
        }
        return 0;
    }
    
};

但是提交上去之后，超时了

屏幕快照 2016-09-16 16.34.10.png

说明思路没有错误，但是排序太慢了，尝试扫描一半：
冒泡排序变成：

 for(int i = 0; i< (nums.size()-1)/2; i++){//这句话 变成了扫描一般
            for(int j = i; j<nums.size()-i; j++){
                if(nums[j] < nums[i]){
                    swap(nums[i], nums[j]);
                }else if(nums[j] > nums[nums.size()-i-1]){
                    swap(nums[j], nums[nums.size()-i-1]);
                }
            }
        }

提交，依旧会时间超限

上网查找排序时间，总结来说，一般快排最快，一提交，果然AC，所以代码如下
<u>Runtime: 26 ms</u>

class Solution {
public:
    vector<int> num;
    
    void quick_sort(int left, int right)
    {
        if(left<right)
        {
            int i = left;
            int j = right;
            int x = num[i];
            
            while(i<j)
            {
                while(i<j&&num[j]>x)
                    j--;
                if(i<j){
                    num[i] = num[j];
                    i++;
                }
                while(i<j&&num[i]<x)
                    i++;
                if(i<j){
                    num[j] = num[i];
                    j--;
                }
            }
            num[i] = x;
            quick_sort(left, i-1);
            quick_sort(i+1, right);
            }  
    }

    int singleNumber(vector<int>& nums) {
        num.clear();
        num = nums;
        quick_sort(0, nums.size()-1);
        for(int i = 0; i < num.size(); i+=2){
            if(i == 0&&num[0]!=num[1]){
                return num[0];
                break;
            }else if(i == num.size()-1&&num[i]!= num[i-1]){
                return num[num.size()-1];
                break;
            }
            else if(num[i]!=num[i+1]){
                return num[i];
                break;
            }
        }
        return 0;
    }
    
};

根据网友启发，发现了一种更简单的方法。
由于n^n=0, 而0^n = n, 所以给定一组数组
可以将所有数进行一起异或，最后剩下的那个数就是single num，时间复杂度为O(N)，代码如下
时间为<u>19ms</u>

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