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?

 

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
     
       res=new HashSet
      
       ();        for(int i=0;i
      
     

Solution 2:

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

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

要熟悉XOR的工作原理

Reference:

 

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 the output 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