Single Element III
给出2*n + 2个的数字,除其中两个数字之外其他每个数字均出现两次,找到这两个数字。
样例
给出 [1,2,2,3,4,4,5,3],返回 1和5
挑战
O(n)时间复杂度,O(1)的额外空间复杂度
Solution
与以上两题不同的是,这道题有两个数只出现一次。基本的思路还是利用位运算,除去出现次数为2次的数。
如果对所有元素进行异或操作,最后剩余的结果是出现次数为1次的两个数的异或结果,此时无法直接得到这两个数具体的值。但是,因为这两个数一定是不同的,所以最终异或的值至少有一个位为1。我们可以找出异或结果中第一个值为1的位,然后根据该位的值是否为1,将数组中的每一个数,分成两个部分。这样每个部分,就可以采用Sing number I中的方法得到只出现一次的数。
利用bitwise XOR的特点,n个数(0或1),如果1的个数为奇数,则n个数bitwise XOR结果为1,否则为0
先将所有的数异或,得到的将是x和y以后之后的值n。 找到这个数n的为1的某一位(为了方便就取最右边为1的一位, n & ~(n-1),再将这一位为1的数异或,其余的数异或,得到的就是x和y的值。
Complexity
时间复杂度 O(n),空间复杂度 O(n)
Code
public class Solution {
/**
* @param A : An integer array
* @return : Two integers
*/
public List<Integer> singleNumberIII(int[] A) {
ArrayList<Integer> res = new ArrayList<Integer>();
res.add(0);
res.add(0);
int n = 0;
for (int elem : A) {
n ^= elem;
}
n = n & (~(n-1));
for (int elem : A) {
if ((elem & n) != 0) {
res.set(0, res.get(0)^elem);
}
else res.set(1, res.get(1)^elem);
}
return res;
}
}