leetcode 128 最长连续序列

使用了并查集的思路。建立一个键值为节点值,值为是否出现过以及对应节点索引的二元组。遍历整个数组的过程中,判断是否有相邻的数出现,如果未出现相邻的数,则将其添加至哈希表中,如果出现了一个相邻的数,则添加至哈希表,并将father数组对应的值改为这个相邻数的“根节点值”,这个节点值通过getfather函数获得,如果两端都有相邻的,则将较小的数对应的根节点值赋给他,然后将较大的相邻的值的根结点同样改为前面较小的书对应的根节点。空间占用好像有点大,贴代码

 1 class Solution {
 2 public:
 3     int getfather(vector<int>& father,int index)
 4     {
 5         while(father[index]!=index)
 6         index = father[index];
 7         return index;
 8     }
 9     int longestConsecutive(vector<int>& nums) 
10     {
11         int n = nums.size();
12         //并查集
13         vector<int> father(n);
14         for(int i = 0 ; i < n ; i++)
15         father[i] = i;
16         //两个哈希表
17         unordered_map<int,pair<bool,int>> numsHash;
18         unordered_map<int,int> sizeHash;
19         //最大值
20         int maxSize = 0;
21         for(int i = 0 ; i < n ; i++)
22         {
23             //只有该数组在哈希中未出现才会考虑
24             if(!numsHash[nums[i]].first)
25             {
26                 if(numsHash[nums[i]-1].first && numsHash[nums[i]+1].first)
27                 {
28                     //cout<<i<<endl;
29                     //向前靠
30                     numsHash[nums[i]] = {true,i};
31                     int index = getfather(father,numsHash[nums[i]-1].second);
32                     father[i] = index;  
33                     //将后一个的合并
34                     int indexLatter = getfather(father,numsHash[nums[i]+1].second);
35                     //cout<<indexLatter<<endl;
36                     father[indexLatter] = index;
37                 }
38                 else if(numsHash[nums[i]-1].first)
39                 {
40                     int index = getfather(father,numsHash[nums[i]-1].second);
41                     father[i] = index;
42                     numsHash[nums[i]] = {true,i};  
43                 }
44                 else if(numsHash[nums[i]+1].first)
45                 {
46                     int index = getfather(father,numsHash[nums[i]+1].second);
47                     father[i] = index; 
48                     numsHash[nums[i]] = {true,i}; 
49                 }
50                 else 
51                 {
52                     //完成在哈希表中赋值
53                     numsHash[nums[i]] = {true,i};
54                 }
55             }
56         }
57         //完成并查集建立,开始计算结果
58         for(int i = 0 ; i < n ; i++)
59         {
60             //cout<<getfather(father,i)<<endl;
61             int currentSize = ++sizeHash[getfather(father,i)];
62             //cout<<currentSize<<endl;
63             if(currentSize>maxSize)
64             maxSize = currentSize;
65         }
66         return maxSize;
67     }
68 };

还有一种很好的方法,首先通过哈希表存储所有的数组元素,这样也能起到去重的作用。之后就对每个数组元素做一件事,在哈希表中查找+1的元素是否存在,重复上述过程直到找不到为止。有一个小细节就是,在查找之前先判断当前节点值-1的数是否存在,如果存在,就代表从自己开始的序列的结果不可能优于自己-1为头的序列。这样就可以很大程度上减少重复查找,贴代码

 1 class Solution {
 2 public:
 3     int longestConsecutive(vector<int>& nums) 
 4     {
 5         unordered_set<int> numsHash;
 6         for(auto temp:nums)
 7         numsHash.insert(temp);
 8         int maxSize = 0;
 9         for(const int& num:numsHash)
10         {
11             if(!numsHash.count(num-1))
12             {
13                 int currentNum = num;
14                 int currentLen = 1;
15                 while(numsHash.count(currentNum+1))
16                 {
17                     currentLen++;
18                     currentNum++;
19                 }
20                 if(currentLen>maxSize)
21                 maxSize = currentLen;
22             }
23         }
24         return maxSize;               
25     }
26 };

 

上一篇:SCNU_数据结构作业_实验5 图的算法与应用


下一篇:2021-11-10