题目
落单的数 III
给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。
样例
给出 [1,2,2,3,4,4,5,3]，返回 1和5
挑战
O(n)时间复杂度，O(1)的额外空间复杂度
解题
根据落单的数I，可以想到，所有的数进行异或运行的结果就是所求两个数的异或结果。
这个异或的结果，二进制数是1的位置说明这两个数对应的二进制位不相同。然后再怎么还原？？？
参考，理解的不是很透，找到第k位后，再判断数组中所以数的第k位是0 还是1，,出现两次的数对求解无影响，通过这个第k为把数组分成两类，也就把两个数分开了，这里的第k位在a、b中一定不相同的，一定是一个0一个1。
public class Solution {
/**
* @param A : An integer array
* @return : Two integers
*/
public List<Integer> singleNumberIII(int[] A) {
// write your code here
int axorb = 0;
LinkedList<Integer> res = new LinkedList<Integer>();
for( int i = 0; i <A.length;i++){
axorb ^= A[i];
}
int a = 0;
int b = 0;
int k = 0;
while( axorb % 2==0){
axorb >>= 1;
k++;
}
for(int i=0;i< A.length;i++){
int tmp =( A[i]>>k)%2;
if(tmp==0)
a ^= A[i];
else
b ^= A[i];
}
res.add(a);
res.add(b);
return res;
}
}
Java Code
总耗时: 3520 ms
class Solution:
"""
@param A : An integer array
@return : Two integer
"""
def singleNumberIII(self, A):
# write your code here
x = 0
for num in A:
x ^= num
a = 0
b = 0
k = 0
while x%2==0:
x = x>>1
k +=1
for num in A:
tmp = (num>>k)%2
if tmp==0:
a ^=num
else:
b ^=num
return [a,b]
Python Code
总耗时: 514 ms
当然对于这样的题目，利用HashMap是最简单不过的了。
public class Solution {
/**
* @param A : An integer array
* @return : Two integers
*/
public List<Integer> singleNumberIII(int[] A) {
// write your code here
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
LinkedList<Integer> res = new LinkedList<Integer>();
for(int i=0;i<A.length;i++){
if(map.containsKey(A[i])){
map.put(A[i],map.get(A[i]) + 1);
}else{
map.put(A[i],1);
}
if(map.get(A[i]) ==2)
map.remove(A[i]);
}
for(Integer k:map.keySet()){
res.add(k);
}
return res;
}
}
Java Code
总耗时: 4318 ms
优化一下
public class Solution {
/**
* @param A : An integer array
* @return : Two integers
*/
public List<Integer> singleNumberIII(int[] A) {
// write your code here
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
LinkedList<Integer> res = new LinkedList<Integer>();
for(int i=0;i<A.length;i++){
if(map.containsKey(A[i])){
map.remove(A[i]);
}else{
map.put(A[i],1);
}
}
for(Integer k:map.keySet()){
res.add(k);
}
return res;
}
}
Java Code
总耗时: 3995 ms
class Solution:
"""
@param A : An integer array
@return : Two integer
"""
def singleNumberIII(self, A):
# write your code here
d = {}
for num in A:
if num in d:
del d[num]
else:
d[num] = 1
return d.keys()
Python Code
总耗时: 586 ms
