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 itwithout using extra memory?

Solution 1:

思路： 用set检验是不是有重复的。把没有重复的加到set里面，有重复的从set里面remove掉 .最后set里面只存在一个数，用iterator给读出来即可。

注意corner case: 数组只有一个数的时候就直接读出。

Time Complexity: O(N)

 public int singleNumber(int[] nums) {        if(nums.length==1)        {            return nums[0];        }        int number=0;        Set<Integer> res=new HashSet<Integer>();        for(int i=0;i<nums.length;i++)        {            if(!res.contains(nums[i]))            {                res.add(nums[i]);            }            else            {                res.remove(nums[i]);                            }        }        for(int single: res)        {            number=single;        }        return number;     }

Solution 2:

没有想出来不用extra space的，参考了discussion

https://discuss.leetcode.com/topic/47560/xor-java-solution/5

要熟悉XOR的工作原理

Reference: http://www.programmerinterview.com/index.php/java-questions/xor-in-java/

X     Y     Output

0     0     0

0     1     1

1     0     1

1     1     0 

Tricks: 0^a=a 2,a^b=b^a 3,a^a=0, a^1=a(inversion)

题目思路：because the xor has three properties. 1,0^a=a 2,a^b=b^a 3,a^a=0
so swapping the number would not change theoutput at the end, we can see the list as all the same numbers are adjacent.the same numbers would be 0 after xor. the one remaining would be the answer.

因为除了一个数之外其他的数都有一个相同的数，所以最后剩下来的就是 0^a=a极其巧妙.

    public int singleNumber(int[] nums) {        int count=0;        for(int i=0;i<nums.length;i++)        {            count^=nums[i];        }        return count;}

136. Single Number