136. Single Number

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

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

思路1：用hash set

public class Solution {
    public int singleNumber(int[] nums) {
        HashSet set = new HashSet();
        for (int i=0;i<nums.length;i++){
            if (set.contains(nums[i])){
                set.remove(nums[i]);
            }else{
                set.add(nums[i]);   
            } 
        }
        Iterator<Integer> it = set.iterator();
        int result = it.next();
        return result;
    }
}

思路2：如果用linear操作还不额外的内存的话，就用XOR操作。known that A XOR A = 0 and the XOR operator is commutative, the solution will be very straightforward.

public class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i<n; i++)
        {
            result ^= nums[i];
        }
        return result;
    }
}