Single Number

Q:
Given an array of integers, every element appears twice except for one. Find that single one.
Could you implement it without using extra memory?

A:
就是先排序，然后两两对比

public class Solution {
    public int singleNumber(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        Arrays.sort(A);
        if(A.length==1){
            return A[0];
        }
        for(int i =0;i+1<A.length;i=i+2){
            if(A[i] != A[i+1]){
                return A[i];
            }
        }
        // now only the last one is not checked. 
        // we can returned it.
        return A[A.length-1];
    }
}

下面是高手做的。  你TND 都傻了吧？？？ 而且人家不用排序(⊙o⊙)哦

public class Solution {
    int singleNumber(int A[]) {  
        int n = A.length;
        if(n<0)return -1;  
        int res = 0;  
        for(int i =0;i<n;i++)  
            res ^= A[i];  
        return res;  
    }  
}

Mistakes:
1: 没有考虑A.length == 1的情况。
 2： 没有考虑， 当i+1 越界的情况。
3：  当排序后，是最后一个single的时候，我们要返回最后一个。

Learned:
1： ^ 运算符

----------------第二遍-----------------只要三行--------------

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

---------3 rd ----------------------

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