并查集维护序列信息
1562. 查找大小为M的最新分组
参考自大佬的视频教程:https://www.bilibili.com/video/BV1Xp4y1v7Nj?p=4
- 用并查集维护
1
的连通信息 - 具体来说:
f[i]
表示i
所在的连续1
的代表节点的位置,这里我们选用的代表节点是连续一段1
右侧第一个0
的位置。思考题:为什么选这个位置呢?能否选其他位置呢? - 并查集维护额外信息:
siz[i]
维护的是某一段连续1
的长度,该段代表节点为i
。 cnt[i]
维护siz[i]==i
的数量,类似于桶排序,cnt[i]=3
表示有3
段连续1
的长度为i
。
code
const int M=1e5+5;
int f[M],siz[M],cnt[M];
class Solution {
public:
int find(int x)
{
if (x!=f[x])
f[x]=find(f[x]);
return f[x];
}
int findLatestStep(vector<int>& arr, int m)
{
int n=arr.size();
for (int i=0;i<=n+1;i++)
{
f[i]=i;
siz[i]=0;
cnt[i]=0;
}
cnt[0]=n;
int ans=-1;
for (int i=0;i<n;i++)
{
int p=arr[i];
f[p]=p+1;
int fp=find(p);
cnt[siz[p]]--;
cnt[siz[fp]]--;
siz[fp]=siz[p]+siz[fp]+1;
siz[p]=0;
cnt[siz[fp]]++;
if (cnt[m])
ans=i+1;
}
return ans;
}
};