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 runtime complexity. Could you implement it without using extra memory?

题目翻译

给出一组整数数组，除了一个元素只出现一次外，其余都出现了两次。找出那个只出现一次的。

注意： 你的算法的时间复杂度应该是线性的。你可以不使用额外的存储空间来完成它吗？

解题方案

标签： Hash Table、Bit Manipulation

思路：

方法一：Hash Table（HashMap-Java）

• 遍历数组，将数组中的元素放入HashMap，无该值则放入，有该值则删除
• 如此，最后只剩下一个键值对，其中的key值就是所求

方法二：Bit Manipulation ：

• 将一个数字和0异或，会得到该数字本身

a ⊕ 0 = a

• 两个相同的数字异或，会得到0

a ⊕ a = 0

• 并且有

a ⊕ b ⊕ a = ( a ⊕ a ) ⊕ b = 0 ⊕ b = b

• 因此，我们可以将所有元素异或来获得特别的那一个
  • 时间复杂度： O(n)
  • 空间复杂度： O(1)

方法三：Math ：

• 使用数学方法，如鸡兔同笼问题的解法。
• 因为只有一个数出现了一次，所以用HashSet获取“头”的数目，出现了两次所以乘以2
• 然后减去遍历数组获取的“脚”的数目，即得到只出现了一次的元素。
  • 时间复杂度: O(n+n)=O(n)
  • 空间复杂度: O(n+n)=O(n)

（ a + b + c ) * 2 - ( a + a + b + b + c ) = c

代码：

//方法一：Hash Table（HashMap）
class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length==0||nums==null){
            return 0;
        }
        HashMap<Integer , Integer> map = new HashMap<Integer , Integer>();
        for(int i=0;i<nums.length;i++){
            if(!map.containsKey(nums[i])){
                map.put(nums[i],1);
            }
            else{
                map.remove(nums[i]);
            }
        }
        for(Map.Entry<Integer, Integer> m : map.entrySet()){
            return m.getKey();
        }
        return 0;
    }
}

//方法二：Bit Manipulation
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            res = res ^ nums[i];
        }
        return res;
    }
}

//方法三：Math
class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length==0||nums==null){
            return 0;
        }
        int sum=0;
        Set<Integer> set= (Set<Integer>) new HashSet();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
            sum+=nums[i];
        }
        int sum2=0;
        Iterator<Integer> ite=set.iterator();
        while(ite.hasNext()){
            sum2+=ite.next();
        }
        int result=2*sum2-sum;
        return result;
    }
}

参考资料

LeetCode- Bit Manipulation LeetCode总结（1） —— 位运算：http://blog.csdn.net/xsloop/article/details/47006241

http://blog.csdn.net/zhning12L/article/details/78271157