Question:
**
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?
**
我一開始的思路很明顯，用哈希表鳞疲。
把數(shù)列的數(shù)字存入哈希表罪郊，然后當(dāng)發(fā)現(xiàn)位置已經(jīng)存了數(shù)字時，表示這個數(shù)字為 twice尚洽，于是我直接將該數(shù)字從哈希表移除。那么最后哈希表就只會剩下一個數(shù)字靶累，他只出現(xiàn)了 once腺毫。 但是也會有問題哈。如果有個數(shù)字是 100000000挣柬，其他的都是很小的數(shù)字潮酒，那么就會浪費空間了。
上代碼
public class Solution {
public int singleNumber(int[] nums) {
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i]))
set.remove(nums[i]);
else
set.add(nums[i]);
}
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i]))
return nums[i];
}
return 0;
}
}
由系統(tǒng)分析可知邪蛔，運算時間比較長急黎。
于是我再次看評論，大神們是怎么做的侧到。于是乎看到了一個勃教，
驚為天人的方法！
我們都知道異或操作匠抗，相同的就會為0故源。然后存在這么一個等式：
**
A XOR B XOR C = A XOR C XOR B = B XOR C XOR A = B XOR A XOR C....
**
也就是說，異或操作遵守交換律汞贸。
那么假想下绳军，數(shù)組里這么多個數(shù)印机，異或，可以把出現(xiàn)兩次的數(shù)排在前面门驾，只出現(xiàn)一次的數(shù)（唯一一個）排在最后射赛。那么前面的異或結(jié)果都是0，直到最后奶是，結(jié)果為這個只出現(xiàn)了一次的數(shù)楣责。
于是我又拿Java重寫了下這個方法。
上代碼
public class Solution {
public int singleNumber(int[] nums) {
int s = 0;
for (int i = 0; i < nums.length; i++)
s ^= nums[i];
return s;
}
}
額诫隅，核心就四行代碼腐魂，算法復(fù)雜度為 O(N),基本沒有用什么空間。然后看系統(tǒng)測的評價
可以看到時間快了逐纬，而且內(nèi)存肯定也少了蛔屹。
但是，還不夠快豁生！
為什么兔毒，因為Java畢竟是建立在JVM上的，所以不能直接控制底層甸箱。那么育叁，
用C重寫吧。也許是今天興致好芍殖，我又重寫了C豪嗽，或者說，比較容易重寫吧豌骏。
上代碼
int singleNumber(int* nums, int numsSize) {
int s = 0;
int i;
for (i = 0; i < numsSize; i++)
s ^= nums[i];
return s;
}
然后看系統(tǒng)的評價
額龟梦，速度一下子上升到了 15ms。窃躲。计贰。這就是C語言，這就是指針的效率啊蒂窒。躁倒。。
**
總結(jié)：
這次作業(yè)還是比較簡單的洒琢。收獲如下吧：
當(dāng)有一大堆重復(fù)數(shù)字時图呢，如果他們的類型同意夫凸，比如 integer疮薇。 那么就可以用異或操作來除去重復(fù)的數(shù)字笤昨，當(dāng)然，只限于該題的情況停士。只不過是一種很好的思路挖帘。
這叫做完丽， Bit Manipulation.
還有，C果然比Java快好多拇舀。逻族。。第一次見識到指針的效率骄崩！
**
這次的題目也還不是很帶勁聘鳞。今天不做啦，明天繼續(xù)要拂。
Good luck, Richardo!
My code:
public class Solution {
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
int curr = nums[0];
for (int i = 1; i < nums.length; i++) {
curr = (curr ^ nums[i]);
}
return curr;
}
}
解法熟記在心了抠璃。。脱惰。
Anyway, Good luck, Richardo!
這道題目一直記得解法搏嗡。。拉一。很巧妙采盒。做法類似，不寫了蔚润。
Anyway, Good luck, Richardo! - 08/05/2016
