解法一：排序
參考：https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/java-pai-xu-ji-he-ha-xi-biao-bing-cha-ji-by-lzhlyl/
分析：
如果這個序列是個有序的序列，那么找到最長連續序列就比較簡單，遍歷一下這個陣列，并做一些處理即可，
代碼：
int longestConsecutive_sort(vector<int>& nums) {
if(nums.size()==0) return 0;
sort(nums.begin(),nums.end());
int maxLen = 1, curLen = 1, lastNum = nums[0];
for(int i=1; i<nums.size(); i++) {
cout<<nums[i];
if(nums[i] == lastNum) continue;
else if(nums[i] == lastNum + 1) curLen++;
else { //連不上了
maxLen = max(maxLen, curLen);
curLen = 1;
}
lastNum = nums[i];
}
maxLen = max(maxLen,curLen);
return maxLen;
}
解法二：集合
分析：
先將陣列中所有的數存入集合，（利用集合O(1)的查找效率，快速判斷集合中是否有某個數的下一個數字）
然后遍歷陣列中所有的數num：
- 看num+1在不在集合中，如果在，再看num+2在不在集合中......,一直找到num+k，
- 每找到一個，就將num作為左邊界的連續序列長度+1，直到num+k不在集合中，即num+k不在陣列中，停止當前num的處理，更新最大長度，處理陣列中的下一個元素，
舉例：陣列為【2 4 5 7 3】，先把五個數都存在集合中，然后遍歷陣列，假如num為2，當前的序列長度就是1，然后取集合中找有沒有3，有的話序列長度就+1，然后找4，找5，最后找不到6，則以2為左邊界的連續序列長度為4，即【2 3 4 5】，
注意：我們可以看到，當2處理完后，下一個處理的就是4，最后處理結果是以4為左邊界的連續序列長度為2（【4 5】），但是我們可以發現，4在處理2的時候已經處理過了，這個計算就沒有必要存在，所以我們可以采取一定的剪枝處理，
剪枝：當處理某一個數num時，先判斷num-1在不在集合（陣列）中，如果陣列中有num-1的話，就跳過當前num的處理，
因為num的處理不僅占用時間，且計算的結果一定是無意義的，對num進行處理后的連續序列的長度如果為m，那m一定不是我們想要的最大長度，因為num-1是在陣列中的，加上num-1后，連續序列長度就變為m+1，我們不知道m+1是不是最后的結果，但至少m一定不是最后的最大長度，所以當存在num-1時，num的處理就被跳過，
代碼：
int longestConsecutive_set(vector<int>& nums) {
unordered_set<int> num_set;
for (const int& num : nums) {
num_set.insert(num); //構建哈希表（集合，unordered_set內部實作為哈希表）
}
int longestStreak = 0;
for (const int& num : num_set) { //遍歷集合
//判斷num-1在不在，防止重復計數，如：對于4，如果集合中有3，則跳過，因為在處理3的時候，會緊接著處理4及4以后的數，避免重復的操作
if (!num_set.count(num - 1)) {
int currentNum = num; //當前處理的數
int currentStreak = 1;
while (num_set.count(currentNum + 1)) { //在哈希表中，查找時間為O(1)
currentNum += 1;
currentStreak += 1;
}
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
解法三：哈希表
分析：
設定一個哈希表，存盤的鍵值對表示如下：
- key：某一個數
- value：在當前已讀取的數字中
- 該數作為邊界時，其所處的最長連續序列的長度，（為了方便描述，我們定義當該數是邊界時，哈希表的值稱為【邊界最大值】）
- 當該數非邊界時，其value無意義，（硬說找到一個意義的話，就是該數上一次作為邊界的時候，當時該數所在的最長連續序列的長度）
這樣的話，我們遍歷整個陣列，當前處理某一個數
num：
如果
num不在哈希表中，即還沒有讀取過：
首先將
num自己看做一個只有自己，長度為1 的連續序列，并將其【邊界最大值】設為1，然后在哈希表中查找，看
num-1和num+1是否在哈希表中：
如果
num-1不在，說明num的左邊沒有需要合并的序列，num需要作為左邊界.如果
num+1不在，說明num的右邊沒有需要合并的序列，num需要作為右邊界.如果
num-1或num+1在哈希表中，說明其已經被訪問過，且哈希表中存的值，是該數的【邊界最大值】（原因：num-1或num+1要么未被訪問，要么作為一個序列的邊界，不可能是被訪問過的非邊界元素）假如當前查找到
num-1在哈希表中，值為4
這就說明，num左邊有一個長度為4的序列可以合并，我們就可以將其合并，并更新【邊界最大值】，只需要更新新合并后的這個更長的連續序列的兩個邊界的【邊界最大值】即可，如果
num已經在哈希表中，直接跳過，訪問下一個元素，
具體實作：
遍歷陣列，如果num已經訪問，則跳過；如果未被訪問，進行下面的處理：
（假如當前已經讀取過的陣列組成的序列為：【 2 3 4】 【7 8 】，當前num為5）
- 先假設num兩邊都沒有可以合并的序列，哈希表中插入<num,1>；
- 查看num左邊可以合并的連續序列的長度
left_total_length：即查找哈希表中 5-1 的值，如果未找到，說明左邊可合并長度為0，（上例中left_total_length為3）- 查看num右邊可以合并的連續序列的長度
right_total_length：即查找哈希表中 5+1 的值，如果未找到，說明右邊可合并長度為0，（上例中right_total_length為0）- 計算合并后的連續序列總長度：total_length = 左 + 1 + 右 = 3 + 1 + 0 =4，表示合并后序列長度為4，即【2 3 4 5】
- 更新
num-left_total_length和num-right_total_length在哈希表中的值為total_length，當right_total_length為0時，就是num作為右邊界，即更新num的【邊界最大值】
代碼：
int longestConsecutive_hashset(vector<int>& nums) {
int res = 0;
int n=nums.size();
//表示該數 作為邊界時的最長連續陣列 的長度，
//當該數非邊界時，其值無意義（或者說是其上一次作為邊界時，當時其所在最長連續陣列的長度）
//如：對于1，1的值為1；對于1234,1和4的值為4, 23的值取決于原陣列的順序，順序不同，其值不同
unordered_map<int,int> count_map;
for(int num : nums) {
//不用考慮 非邊界數字 的值 的影響，因為其如果不是邊界，表示已經讀取到它左邊或右邊的數字，并將它們作為了邊界，
//對于距離邊界最近 的非邊界元素，也就是邊界旁邊的元素，這個時候邊界也已經入表，已經沒有別的情況需要考慮非邊界的數值了
if(count_map.count(num)==0) {
//獲取左右挨著的兩個數，獲取他們當前最長連續陣列的長度
int left_total_length = count_map.count(num-1)!=0?count_map[num-1]:0; //c++中取某個key的value，如果沒有就是0
int right_total_length = count_map.count(num+1)!=0?count_map[num+1]:0;;
//將當前讀取數字入表，表示已經處理過該數字，這個值無所謂，是多少都行，
//因為如果num不是邊界，左右數都已經入表，那以后再也用不到num的值，如果是邊界，在下面更新操作中也會對num 的值進行更新
//處于科學一點的角度，取值為1
count_map[num] = 1;
//左 + 1 + 右
//例：1234 678 ，當前num為5，則左為4，右為6，都在表中，且4的值為4,6的值為3，則加上5后，總長度為4+1+3
int total_length = left_total_length+1+right_total_length;
//更新為最大
res = max(res , total_length);
//更新邊界
//上例：1234 678，num為5，更新 [5-4]和[5+3] 即邊界1和8的值為當前新的總長度
count_map[num-left_total_length] = total_length;
count_map[num+right_total_length] = total_length;
}
}
return res;
}
解法四：并查集
參考：https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/java-pai-xu-ji-he-ha-xi-biao-bing-cha-ji-by-lzhlyl/
分析：
并查集基礎知識在 資料結構：并查集
思路：
- 初始狀態：所有元素 各自組成 集合，集合中只有自己一個元素
- 第一次遍歷：將
num所在的集合 合并到num+1所在的集合- 如果
num+1存在，則合并，以num+1所在集合的根節點為合并后的根，
- 在并查集中的根節點，就代表當前集合中的最大元素
- 在本題的背景下，并查集中的根節點表示的是一個連續序列的右邊界
- 舉例：此時存在兩個集合【1 2 3】【4 5】，此時遍歷到num為3，即將3所在集合合并到4所在集合，集合【123】的father為3，【45】的father為5，合并后5為兩個集合的新father，
- 在演算法中，可以利用一個回圈，將上面【123】的father都改為新根5，避免后續尋找根節點時，層次過深，
- 如果
num+1不存在，則跳過，- 第二次遍歷：記錄所有人與其father的距離，即與其所處連續序列右邊界的距離
- 距離 = 右邊界 - 當前元素 +1
代碼：
class UnionFind {
private:
unordered_map<int,int> father;
public:
void init(vector<int> nums) {
for(int i = 0; i<nums.size(); i++) {
father.emplace(nums[i],nums[i]);
}
}
int find(int x) {
if(father.count(x) == 0) return INT_MAX;
//原本并查集中，如果沒有找到father，回傳NULL
//但是 C中 0==NULL，如果一個元素的father是0，也會被認為沒有找到
//進而題中元素的范圍只在-10^9 <= nums[i] <= 10^9 之間，所以，在沒有找到father的時候，回傳INT_MAX代替NULL
//遞回的向上找father
int root = x;
while(root != father[root]) root = father[root];
//扁平化處理：從x到father，路徑上所有的結點的father都改為整個集合的father，即root
while(x != father[x]) {
int cur = x;
x = father[x];
// father.emplace(cur,root); //emplace 插入時，key存在則不變，就是這個地方導致超時
father[cur] = root;
}
return root;
}
void merge_union(int x, int y) {
//y合并到x內，即x的根節點作為合并后的總根
x = find(x);
y = find(y);
if(x == y) return;
if(x==INT_MAX || y==INT_MAX) return;
father[y] = x;
}
void print_ufset() {
for(unordered_map<int,int>::iterator it=father.begin(); it!=father.end(); it++)
cout<<"num: "<<it->first<<" father: "<< it->second<<endl;
}
};
int longestConsecutive_unionfind(vector<int>& nums) {
if(nums.size()==0) return 0;
UnionFind uf;
uf.init(nums);
for(int num:nums){
uf.merge_union(num+1,num); //num的集合 合并到num+1 的集合中
}
int maxLen = 1;
for(int num:nums){
maxLen = max(maxLen , uf.find(num) - num +1);
}
return maxLen;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/285754.html
標籤：其他