给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4

暴力算法

可以先统计出各个元素出现的次数，然后找到那个次数等于 1 的元素：

  1. public int singleNumber(int[] nums) {
  2.     Map<Integer, Integer> countMap = countNum(nums);
  4.     for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
  5.         if (entry.getValue() == 1) {
  6.             return entry.getKey();
  7.         }
  8.     }
  10.     return -1;
  11. }
  13. private Map<Integer, Integer> countNum(int[] nums) {
  14.     Map<Integer, Integer> countMap = new HashMap<>();
  15.     for (int num : nums) {
  16.         if (!countMap.containsKey(num)) {
  17.             countMap.put(num, 1);
  18.         } else {
  19.             countMap.put(num, countMap.get(num) + 1);
  20.         }
  21.     }
  22.     return countMap;
  23. }

暴力算法借助了额外的空间，如果不借助额外空间就需要借助特别操作！

或运算有两种情况的计算结果为 true：
情况1：一个为 treu，另一个为 false
情况2：两个都为 true

其中情况1也可以专门称为 异或运算，而异或运算就有个常见的用途：判断两个值是否不同！

  1. 0 ^ 0 = 0
  2. 0 ^ 1 = 1
  3. 1 ^ 0 = 1
  4. 1 ^ 1 = 0

异或运算有如下几个运算定律：
1）一个值与自身的运算，总是为 false x ^ x = 0
2）一个值与 0 的运算，总是等于其本身 x ^ 0 = x
3）可交换性 x ^ y = y ^ x
4）结合性 x ^ (y ^ z) = (x ^ y) ^ z

比如：

  1. a ^ b ^ c ^ a ^ b
  2. = a ^ a ^ b ^ b ^ c
  3. = 0 ^ 0 ^ c
  4. = c
  1. public int singleNumber(int[] nums) {
  2.     int ans = nums[0];
  3.     if (nums.length > 1) {
  4.         for (int i = 1; i < nums.length; i++) {
  5.             ans = ans ^ nums[i];
  6.         }
  7.     }
  8.     return ans;
  9. }