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毫秒,非常棒的解法!