題目
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?
分析
數組中所有數都出現2次，除了某個數隻出現1次，求出這個數
解答
解法1：（我）HashMap，使用了額外的記憶體（15ms ×）
key為元素值，value為1，重複的元素删掉，最後隻剩下一個元素
public class Solution {
public int singleNumber(int[] nums) {
HashMap hashMap = new HashMap<Integer, Integer>(((int)(nums.length / 0.75) < 16) ? 16 : (int)(nums.length / 0.75));
int result = 0;
for (int num : nums){
if(hashMap.containsKey(num)){
hashMap.remove(num);
}
else{
hashMap.put(num,1);
}
}
Set set = hashMap.keySet();
Iterator iterator = set.iterator();
while(iterator.hasNext()){
result = (Integer)iterator.next();
}
return result;
}
}
解法2：二進制異或運算（1ms√）
>1. 0 ^ N = N
>2. N ^ N = 0
是以，如果N是single number，
N1 ^ N1 ^ N2 ^ N2 .............. Nx ^ Nx ^ N
= (N1^N1) ^ (N2^N2) .............. (Nx^Nx) ^ N
= 0 ^ 0 ^ ..........^ 0 ^ N
= N
public class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums){
result ^= num;
}
return result;
}
}