leetcode 128最長連續序列

?

方法一：使用快排：

//排序法，時間O(nlogn)，使用STL，只是驗證一下思想，非正解；
class Solution {
public:int longestConsecutive(vector<int>& nums) {sort(nums.begin(),nums.end());int res=0;for(int i=0;i<nums.size();i++){int step=0,len=1;while(i+step!=nums.size()-1&&nums[i+step+1]-nums[i+step]<=1){if(nums[i+step]+1==nums[i+step+1]) len++;step++;}res=max(res,len);i+=step;}return res;}
};

?方法二：使用并查集如題所說達到O(n)

?

方法三：使用哈希表O(n)

//哈希表結合染色，建立一個哈希表，然后遍歷之后計數每個元素周圍所有相鄰元素并染色，記錄個數；O(n)復雜度
class Solution {
public:int longestConsecutive(vector<int>& nums) {int len=nums.size();if(len<=1) return len;unordered_map<int,int> m;int res=0;for(int n:nums)m[n]=1;for(int n:nums){int i=n,j=n;int cnt=1;if(m[n]==0)continue;elsem[n]=0;while(m[i+1]==1){i++;m[i]=0;}while(m[j-1]==1){j--;m[j]=0;}cnt=i-j+1;res=cnt>res?cnt:res;}return res;}
};

別人家的哈希表：

/****
通過哈希表記錄邊界信息neither i+1 nor i-1 has been seen: m[i]=1;both i+1 and i-1 have been seen: extend m[i+m[i+1]] and m[i-m[i-1]] to each other;only i+1 has been seen: extend m[i+m[i+1]] and m[i] to each other;only i-1 has been seen: extend m[i-m[i-1]] and m[i] to each other.*****/
class Solution {
public:int longestConsecutive(vector<int>& nums) {int len=nums.size();if(len<=1) return len;unordered_map<int,int> m;int res=0;for(int i:nums){if(m[i]) continue;//后面表達式為將m[i]和這一段連續序列的邊界全部賦值為他的長度//邊界只可能為m[i-m[i-1]]到m[i+m[i+1]]，m[i]到m[i+m[i+1]],m[i-m[i-1]]到m[i]這幾種情況，因此更新三者的值為新連續序列的長度即可//又因為沒有的元素哈希值為0，所以m[i]左右元素的m[i-1]+m[i+1]+1為新序列的長度；res=max(res,m[i]=m[i+m[i+1]]=m[i-m[i-1]]=m[i-1]+m[i+1]+1);}return res;}
};

?別人家的使用hashset 和 hashtable：

hashset：

/****
通過哈希set將nums轉化為哈希set,然后對哈希set進行遍歷，尋找連續片段的左邊界，然后num+1進行遍歷。
可以證明每個元素將被訪問2遍，for中一遍，while一遍，所以time O(n),space O(n);
由于int會產生越界，可以使用long,也可以進行邊界檢測，INT_MAX break;*****/
class Solution {
public:int longestConsecutive(vector<int>& nums) {int res=0;unordered_set<int> h(nums.begin(),nums.end());for(int num:nums){int l=0;if(!h.count(num-1)){while(h.count(num)!=0){++l;if(num==INT_MAX) break;++num;}res=res>l?res:l;}}return res;}
};

hashtable：

/****
通過哈希tablesolution 1: hashtable (key,len)
case1: no neighboors
h[num]=1;
case2: one neighboor
l=h[num-1] or r=h[num+1]
h[num]=h[num-1]=l+1 or h[num]=h[num+1]=r+1
case3: two neighboors
l=h[num-1]
r=h[num+1]
h[num]=h[num-1]=h[num+1]=l+r+1*****/
class Solution {
public:int longestConsecutive(vector<int>& nums) {int res=0;unordered_map<int,int> h;for(int num:nums){if(h[num]!=0) continue;int l=h[num-1];int r=h[num+1];int t=l+r+1;h[num]=h[num+r]=h[num-l]=t;res=res>t?res:t;}return res;}
};

?哈希set

/****
通過哈希set將nums轉化為哈希set,然后對哈希set進行遍歷，尋找連續片段的左邊界，然后num+1進行遍歷。
可以證明每個元素將被訪問2遍，for中一遍，while一遍，所以time O(n),space O(n);
由于int會產生越界，可以使用long,也可以進行邊界檢測，INT_MAX break;*****/
class Solution {
public:int longestConsecutive(vector<int>& nums) {int res=0;unordered_set<int> h(nums.begin(),nums.end());for(int num: nums){int l=0;if(h.count(num-1)==0){while(h.count(num)>0){l++;if(num==INT_MAX) break;num++;}}res=res>l?res:l;}return res;}
};

?

有道詞典

solution 1: has ...

詳細X

解決方案1:哈希表(關鍵,len) case1:沒有neighboorsh (num) = 1,例2:一個neighboorl = h [num-1]或r = h (num + 1) h (num) = h [num-1] = l + 1或h (num) = h (num + 1) = r + 1 case3:兩個neighboorsl = h [num-1] r = h (num + 1) h (num) = h [num-1] = h (num + 1) = l + r + 1 　　 　　 　　* * * * * /類解決方案{公眾:int longestConsecutive(向量< int > & num) {int res = 0; unordered_map < int, int > h;為(int num: num){如果(h (num) ! = 0)繼續;int l = h [num-1]; int r = h (num + 1); int t = l + r + 1; h (num) = h (num + r) = h [num-l] = t; res = res > t ? res: t;}返回res;}};