程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [Leetcode]Single Number

[Leetcode]Single Number

編輯:C++入門知識

[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;
	}
};

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved