OJ:https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
题目
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
限制
2 <= nums <= 10000
Set容器解法
看到这个题目，我最先想到的是Set容器——一个只能存无重复元素的数组，我们可以利用java，Set容器的add（）方法的boolean型返回参数，在将nums中的元素逐个插入Set的过程中，会发生两种情况：
- 返回ture表示插入成功，证明之前没有出现过这个数。
- 返回false表示插入失败，说明Set中已有这个元素，我们要做的就是在Set中删掉这个元素。
最后，Set里剩下的就是组不成对儿的两个数了。
上代码：
class Solution {
public int[] singleNumbers(int[] nums) {
Set<Integer> s = new HashSet<>();
for(int i=0;i<nums.length;i++) {
if(!s.add(nums[i]))s.remove(nums[i]);
}
Iterator<Integer> i = s.iterator();
int[] res = new int[2];
res[0] = i.next();
res[1] = i.next();
return res;
}
}
提交结果
看着结果还不错，然而，有大神给出了更高性能的异或解法。
异或解法
在了解异或解法之前，首先要知道一点异或的性质：
- n^n=0 一个数异或自己为等于零
- n^0=n 一个数异或零等于它本身
着能说明什么呢？看下面的栗子：
j ^ m ^ y ^ r ^ e ^ y ^ j ^ m
这个式子会得到什么？它们之中相同数两两会异或为零，最后剩下:
e ^ 0 = e
所以，当一串数之中只存在一个不同的值的时候，只需连续异或就能把它找出来。【1】
但是，这道题要找的是两个不同的数，我们可以通过与&1分奇偶类似的方式将nums分为两组，每组都包含一个不同的值，怎么做到呢？
总之先异或一遍：先把nums里的数挨个异或一遍，这样我们肯定会得到一个非零的值（因为存在两个不同的数，相异或一定不为零）
分类：使用这个数的最低位1作为分类的依据，如 示例中6(110)和1(001)的异或结果为001，那么使用001对nums中的每个元素进行异或，结果为0的作一组，结果为1的作一组，就可以把6和1分在不同的两组，且这两组数一定只有1（或6）不成对，因为相同的数&001的结果是一样的,会被分在统一组。（如果是不同的数是5(101)和3(011)，取它们异或结果的最低位1——010，也能达到同样的效果）
3.得出结果：根据上边的【1】，把两个分好类的数组进行异或，很容易的得到最终要找的不同的数了。
上代码：
class Solution {
public static int[] singleNumbers_best(int[] nums) {
//k存异或的结果
int k = 0;
for (int num : nums)
k ^= num;
//mask从0001开始把1左移，当mask&k!=0说明碰到了最低位的1
int mask = 1;
while ((k & mask) == 0)
mask <<= 1;
//分类和找结果同时进行了
int a = 0;
int b = 0;
for (int num : nums) {
if ((num & mask) == 0) {
a ^= num;
} else {
b ^= num;
}
}
return new int[] { a, b };
}
}
提交结果
内存都和Set差不多，但是快了9毫秒，非常棒的解法！
