[Leetcode]Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

最近兩個月事情很多，論文開題，家庭變故，都沒有時間學習、做題，也沒有時間寫博客。現在回來再看感覺自己之前很多東西都做的不到位，所以把之前做過的題目也都翻出來做一下，溫故知新嘛~

現在回憶一下，這是我做的第一道leetcode題目，也是我最初接觸算法的時候做的。當時拿到題目簡直是丈二和尚，感覺被leetcode的高深莫測深深折服了。後來想了很久感覺用本科二年級學過的數據結構裡的哈希表可以解決這個問題，但是苦於c++水平太低，對關聯容器這種外星物種更是一無所知，所以就一直沒能實現。然後就開始猥瑣的上網搜答案，答案一邊倒倒向用位運算——異或解決這個問題，又一次感覺自己的智商被碾壓。

任何數和它本身異或都得零，看到這句話瞬間感覺好猥瑣（可以腦補屌絲碼農自我安慰的場景，事後四大皆空，更不可能有孩子）。任何數和零異或都得它本身，這......屌絲終歸是屌絲TT

言歸正傳，下邊是這個思路的代碼

 

class Solution{
public:
	int singleNumber(int A[], int n) {
		int answer = A[0];
		for(int i = 1;i < n; i++){
			answer = answer ^ A[i];
		}
		return answer;
	}
};

再說哈希表的思路，後來用了關聯容器map來實現，自己測試過了，但是OJ系統報存儲空間溢出。這次溫習又用同樣的方法嘗試了下竟然過了，雖然這個方法空間復雜度是O（n），但總覺得這個方法比較實在，或者說比較通用，改變數組元素的重復次數依然使用（而位運算不行）用它也可以解決Single Number II。下面是代碼：

 

 

class Solution{
public:
	int singleNumber(int A[], int n) {
		map m;
		for (int i = 0; i < n; i++){
			if (m.count(A[i])){
				m[A[i]]++;
			}
			else{
				m[A[i]] = 1;
			}
		}
		for (map::iterator it = m.begin(); it != m.end(); it++){
			if (it->second == 1) return it->first;
		}
		return 0;
	}
};