Given a non-empty 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?

Example 1:
Input: [2,2,1]
Output: 1

Example 2:
Input: [4,1,2,1,2]
Output: 4

求解

大脑的思考过程
这题拿到手，第一反应是用hash表，没有思考细节，只是觉得hash表肯定是可以搞定的，但是空间复杂度是O(n)，不满足题意。

接着开始思考，如何才能做到空间复杂度是 O(1)呢？脑袋开始疯狂打转，但没有思路。没办法，退回原点。

心想，如果使用暴力破解法，该如何解决，很简单：每次从数组中取一个数，记为cur，然后从剩下的数中查找，如果找不到，则cur即为要找的那个数。这种解法时间复杂度是 O(n^2)。

继续思考，如何再继续降低复杂度呢？ 想到了排序 ！！！

再继续思考，如何能把时间复杂度降到 O(n)，有两个突破点：

  • 暴力解法做了很多重复的工作
  • 要充分利用题目的已有信息

通过第一点，我没有想到思路，不知道有没有 DP 的解法，可能本人对DP使用不是太熟。
通过第二点，我还真找到突破口。反复看了好几篇题目，找到了一个很重要的信息：除了某个元素只出现一次以外，其余每个元素均出现两次。 觉得这是个突破口！！！！——异或运算！

解法一：暴力查找
两次循环，代码略

解法二：排序
使用快排，复杂度 O(nlogn)

解法三：
利用 Hash 表，Time: O(n) Space: O(n)

解法四：异或

1、采用数组

未通过

  1. class Solution {
  2.     public int singleNumber(int[] nums) {
  3.         int[] arr = new int[nums.length];
  4.         for(int i = 0; i < nums.length; i++){
  5.             arr[nums[i]] ++;
  6.         }
  7.         for(int i = 0; i < arr.length; i++){
  8.             if(arr[i] == 1){
  9.                 return i;
  10.             }
  11.         }
  12.         return -1;
  13.     }
  14. }

2、异或

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) res ^= num;
        return res;
    }
}

3、HashSet

题目中让我们在线性的时间复杂度内求解，那么一个非常直接的思路就是使用 HashSet，利用其常数级的查找速度。遍历数组中的每个数字，若当前数字已经在 HashSet 中了，则将 HashSet 中的该数字移除，否则就加入 HashSet。这相当于两两抵消了，最终凡事出现两次的数字都被移除了 HashSet，唯一剩下的那个就是单独数字了

题目中让我们不使用额外空间来做，本来是一道非常简单的题，但是由于加上了时间复杂度必须是 O(n)，并且空间复杂度为 O(1)，使得不能用排序方法，也不能使用 HashSet 数据结构。

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> st = new HashSet<>();
        for (int num : nums) {
            if (!st.add(num)) st.remove(num);
        }
        return st.iterator().next();
    }
}

拓展

image.png