题目
落单的数 III
给出2*n + 2个的数字,除其中两个数字之外其他每个数字均出现两次,找到这两个数字。
样例
给出 [1,2,2,3,4,4,5,3],返回 1和5
挑战 Java Code Python Code Java Code Java Code Python Code
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 hereint 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];elseb ^= A[i];}res.add(a);res.add(b);return res;} }
总耗时: 3520 ms
class Solution:"""@param A : An integer array@return : Two integer"""def singleNumberIII(self, A):# write your code herex = 0for num in A:x ^= numa = 0b = 0k = 0while x%2==0:x = x>>1k +=1for num in A:tmp = (num>>k)%2if tmp==0:a ^=numelse:b ^=numreturn [a,b]
总耗时: 514 ms
当然对于这样的题目,利用HashMap是最简单不过的了。
public class Solution {/*** @param A : An integer array* @return : Two integers*/public List<Integer> singleNumberIII(int[] A) {// write your code hereHashMap<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;} }
总耗时: 4318 ms
优化一下
public class Solution {/*** @param A : An integer array* @return : Two integers*/public List<Integer> singleNumberIII(int[] A) {// write your code hereHashMap<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;} }
总耗时: 3995 ms
class Solution:"""@param A : An integer array@return : Two integer"""def singleNumberIII(self, A):# write your code hered = {}for num in A:if num in d:del d[num]else:d[num] = 1return d.keys()
总耗时: 586 ms