Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
public class Solution {
public int singleNumber(int[] A) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
if(A.length == 0 || A == null){
return 0;
}
for(int i=0;i<A.length;i++){
if(map.containsKey(A[i])){
int value = map.get(A[i]);
map.put(A[i], value+1);
}else {
map.put(A[i], 1);
}
}
for(int i=0;i<A.length;i++){
int value = map.get(A[i]);
if(value == 1){
return A[i];
}
}
return 0;
}
}
解法2
异或：相同为0 不同为1
0和a数异或都是a
a和a异或就是0
由于每个数有两个 所以总会相见一次 所以还是0
public class singleNumber {
/**
* @param args
*/
public static void main(String[] args) {
int a[]={1,-1,3,3,4,1,5,5,-1,6};
System.out.println(singleNumber(a));
}
// 异或
public static int singleNumber(int[] A) {
int res = 0;
for (int i : A) {
res ^= i;
}
return res;
}
}
*