Leetcode No. 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?

题目很简单，给一个数组，数组中的数两个一对，只有一个数是狗，要求这个数。
但是后面给出的要求，1. 最好是O(N)的时间复杂度；2. 不能用掉多余的内存；

解题思路有三种：
1. 写两个for循环，来遍历，找单个的元素，这个时间复杂度肯定是O(N2)了；
2. 用一个Set来存元素，已经存在就移除，不存在就放进去，到最后肯定只有一个元素，但是这个用掉了多余空间；
3. 用Arrays.sort()排个序，两两比较，不同的那个就出来了，还是需要循环。

看了答案才知道，使用^，这个逻辑运算符来处理；
1. 异或可交换，即 a ^ b = b ^ a
2. a ^ 0 = a
所以把所有的都拿来异或一下，就剩下落单的元素了。

思考：算法题目大多是数学题，在考虑加减乘除的同时，也要想想离散数学的东西。

附上代码：

import java.util.HashSet;
import java.util.Set;

public class SingleNumber {

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    SingleNumber sn = new SingleNumber();
    int[] nums = {1, 2, 3, 4, 1, 3, 2, 4, 8};
    System.out.println(sn.singleNumber(nums));
    System.out.println(sn.singleNumber2(nums));
  }

  public int singleNumber(int[] nums) {
    if(nums == null || nums.length == 0) {
      return 0;
    }
    Set<Integer> 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]);
      }
    }
    return set.iterator().next();
  }

  public int singleNumber2(int[] nums) {
    if(nums == null || nums.length == 0) {
      return 0;
    }
    int num = 0;
    for(int i = 0; i < nums.length; i++) {
      num = nums[i] ^ num;
    }
    return num;
  }
}