原题链接:力扣 - 每棵子树内缺失的最小基因值[1]
解释一下什么是 mex 值:
mex(S) 的值为集合 S 中没有出现过的最小自然数。例如,mex({1,2}) = 0、mex({0,1,2,3}) = 4
有一棵根节点为 0 的 家族树 ,总共包含 n 个节点,节点编号为 0 到 n - 1 。给你一个下标从 0 开始的整数数组 parents ,其中 parents[i] 是节点 i 的父节点。由于节点 0 是 根 ,所以 parents[0] == -1 。
总共有
个基因值,每个基因值都用 闭区间 [1,
] 中的一个整数表示。给你一个下标从 0 开始的整数数组 nums ,其中 nums[i] 是节点 i 的基因值,且基因值 互不相同 。
请你返回一个数组 ans ,长度为 n ,其中 ans[i] 是以节点 i 为根的子树内 缺失 的 最小 基因值。
节点 x 为根的 子树 包含节点 x 和它所有的 后代 节点。
示例 1:
输入:parents = [-1,0,0,2], nums = [1,2,3,4]
输出:[5,1,1,1]
解释:每个子树答案计算结果如下:
- 0:子树包含节点 [0,1,2,3] ,基因值分别为 [1,2,3,4] 。5 是缺失的最小基因值。
- 1:子树只包含节点 1 ,基因值为 2 。1 是缺失的最小基因值。
- 2:子树包含节点 [2,3] ,基因值分别为 [3,4] 。1 是缺失的最小基因值。
- 3:子树只包含节点 3 ,基因值为 4 。1是缺失的最小基因值。
示例 2:
输入:parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
输出:[7,1,1,4,2,1]
解释:每个子树答案计算结果如下:
- 0:子树内包含节点 [0,1,2,3,4,5] ,基因值分别为 [5,4,6,2,1,3] 。7 是缺失的最小基因值。
- 1:子树内包含节点 [1,2] ,基因值分别为 [4,6] 。1 是缺失的最小基因值。
- 2:子树内只包含节点 2 ,基因值为 6 。1 是缺失的最小基因值。
- 3:子树内包含节点 [3,4,5] ,基因值分别为 [2,1,3] 。4 是缺失的最小基因值。
- 4:子树内只包含节点 4 ,基因值为 1 。2 是缺失的最小基因值。
- 5:子树内只包含节点 5 ,基因值为 3 。1 是缺失的最小基因值。
示例 3:
输入:parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
输出:[1,1,1,1,1,1,1]
解释:所有子树都缺失基因值 1 。
提示:
思路一:集合mex值/dfs分析
这里主要参考了大佬的分析[2]:
既然自底向上更新涉及到大量的集合合并操作,自顶向下更新是不是就会避免这个问题呢?答案是肯定的(至少对于这道题来说是的)。
那么现在考虑自顶向下的更新方式,为了更快的查找最小未出现的数字,初始化一个集合notExist
,存放的是整棵树中未出现的数字,那么每次遍历到一个节点时,只需要返回这个集合中的最小值,然后将该节点的值加入集合中。
初始化方式如下:
unordered_set<int> exist;
set<int> notExist;
int mx;
for(int x: nums) {
mx = max(mx, x);
exist.insert(x);
}
for(int i = 1; i <= mx+1; ++i) { //最大为mx+1
if(!exist.count(i)) {
notExist.insert(i);
}
}
但是这样会出现一个问题,左右子树的更新顺序会影响其答案的正确性,比如先更新左子树,那么右子树中的节点值尚未加入集合notExist
中,那么左子树中节点的mex
值可能就是错误的。如果该节点的mex
值比其他未加入集合notExist
中的值都小,那么该值是正确的,反之该值应该为未加入集合中的那些值中的最小值。现在考虑一个节点的右子树中节点的正确性,由于右子树更新时,左子树中的节点已经加入了集合notExist
中,那么右子树的根节点的答案肯定是正确的。
所以提出了这样一个设想,分别独立跑两次先序遍历,一次先更新左子树,一次先更新右子树,然后将两次结果取较小值即为答案。因为这样能保证对每个节点的mex
值来说,总有一次的值是正确的,而正确的那个总是两者中较小的那个。
class Solution {
int n;
vector<int> res;
set<int> notExist1, notExist2; // 注意这里 set 是有序的
vector<vector<int>> tree;
public:
//根左右遍历
void dfs1(int cur, vector<int>& nums) { // cur 是根,代表一棵子树
res[cur] = min(res[cur], *notExist1.begin()); // 求 mex ,即 当前子树已有答案 与 左遍历下不存在集合最小值 的最小值
notExist1.insert(nums[cur]); // 往下走,相当于抠去了这个节点的值,因此 insert 到 左遍历下不存在集合 里
for(int v : tree[cur]) {
dfs1(v, nums);
}
}
//根右左遍历
void dfs2(int cur, vector<int>& nums) {
res[cur] = min(res[cur], *notExist2.begin());
notExist2.insert(nums[cur]);
for(int i = (int)tree[cur].size() - 1; i >= 0; --i) {
int v = tree[cur][i];
dfs2(v, nums);
}
}
vector<int> smallestMissingValueSubtree(vector<int>& fa, vector<int>& nums) {
n = fa.size();
res.resize(n, 1e6);
tree = vector<vector<int>> (n);
for(int i = 0; i < n; ++i) {
if(fa[i] >= 0) {
tree[fa[i]].emplace_back(i); // 为了自顶向下,建立 {父节点: [子节点集合]} 映射
}
}
unordered_set<int> exist;
int mx = 0;
for(int x : nums) {
mx = max(mx, x);
exist.insert(x);
}
notExist1.clear();
notExist2.clear();
for(int i = 1; i <= mx + 1; ++i) {
if(!exist.count(i)) {
notExist1.insert(i);
notExist2.insert(i);
} // 现在 notExist1 和 notExist2 里是整棵树的未出现过的数
}
dfs1(0, nums);
dfs2(0, nums);
return res;
}
};
为数值的最大值
思路二:dfs序/主席树
主要参考大佬的视频[3]:
咱首先看一看啥是 dfs 序:
如上,每个节点多了两个属性:(i: 在dfs中被第几次遍历到的, j: 在dfs中被遍历到了,且没有子树继续探索了)
,如果该点是叶子节点,则 j
等于 i
,如果该点不是叶子节点,则 j
为自己最后一个子节点的 j
。
dfs 序则有一个很神奇的性质:
如上,我们给每个节点按照 i
排序,如果我们想访问以节点 2
(dfs序为(3, 4)
) 为根的子树,我们只需要遍历dfs序i
处于区间[3, 4]
的节点们就好了。
如上,我们就把子树集合变为了区间表达。
对于本题,如上,依着 dfs 序建立主席树,每棵主席树维护的是基因值的 [1, 1e5]
的区间。假设我们现在想知道节点 2
(dfs序为(3, 4)
) 的基因信息,则我们用主席树 4
减去主席树 2
得到 [3, 4]
的基因信息,然后求和(看是否连续),再二分看 mex 值就行了。(这里主席树没太看懂,系统学到再说吧)
const int MAXN = 1e5 + 50;
vector<int> edge[MAXN]; // 树结构
int iDfs[MAXN], oDfs[MAXN], dfn, rDfs[MAXN]; // dfs 序
int root[MAXN]; // 主席树
void dfs(int x, int father){
iDfs[x] = ++dfn; rDfs[dfn] = x; // rDfs 是反查, reverse dfs 表示 dfs 序对应哪个节点
for (int v: edge[x]) dfs(v, x);
oDfs[x] = dfn; // 子节点遍历完了,离开时, dfs 序是多少,记录下来
}
struct BTree{
int ch[2], sum;
}tree[MAXN * 100];
int numn;
void init(int x, int prev){
tree[x].ch[0] = tree[prev].ch[0];
tree[x].ch[1] = tree[prev].ch[1];
tree[x].sum = tree[prev].sum;
}
void insert(int& x, int y, int left, int right, int v){
x = ++numn;
tree[x].ch[0] = tree[y].ch[0];
tree[x].ch[1] = tree[y].ch[1];
tree[x].sum = tree[y].sum + 1;
if (left == right) return;
int mid = (left + right) / 2;
if (v <= mid)
insert(tree[x].ch[0], tree[y].ch[0], left, mid, v);
else{
insert(tree[x].ch[1], tree[y].ch[1], mid + 1, right, v);
}
}
int query(int x, int y, int left, int right, int l, int r){
if (x == 0 && y == 0) return 0;
if (l <= left && right <= r){
int ret = 0;
if (x != 0) ret = tree[x].sum;
if (y != 0) ret -= tree[y].sum;
return ret;
}else{
int mid = (left + right) / 2;
int ret = 0;
if (l <= mid) ret += query(tree[x].ch[0], tree[y].ch[0], left, mid, l ,r);
if (mid + 1 <= r) ret += query(tree[x].ch[1], tree[y].ch[1], mid + 1, right, l, r);
return ret;
}
}
class Solution {
public:
vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {
int n = parents.size();
for (int i = 0; i <= n; i++) edge[i].clear(), iDfs[i] = oDfs[i] = 0, root[i] = 0; // 清空
for (int i = 1; i < n; i++) edge[parents[i]].push_back(i); // 建树
dfn = 0; dfs(0, -1);
// 下面是更新主席树
tree[0].sum = tree[0].ch[0] = tree[0].ch[1] = 0;
numn = root[0] = 0;
for (int i = 1; i <= n; i++) insert(root[i], root[i - 1], 1, 1e5, nums[rDfs[i]]);
vector<int> ans;
for (int i = 0; i < n; i++){
int left = 1, right = 1e5, rec = 0;
while(left <= right){
int mid = (left + right) / 2;
int ret = query(root[oDfs[i]], root[iDfs[i] - 1], 1, 1e5, 1, mid);
if (ret == mid){
rec = max(rec, mid);
left = mid + 1;
}else right = mid - 1;
}
ans.push_back(rec + 1);
}
return ans;
}
};
本题还有其他两个解法,很妙,这里摘抄一下巨佬的go语言题解[4]如下两个。
思路三:启发式合并
遍历整棵树,统计每棵子树包含的基因值集合,以及缺失的最小基因值(记作
)。合并基因值集合时,总是从小的往大的合并(类似并查集的按秩合并),同时更新当前子树的
的最大值。合并完成后再不断自增子树的
直至其不在基因值集合中。
这一方法同时也适用于有相同基因值的情况。
时间复杂度:
。证明[5]。
func smallestMissingValueSubtree(parents []int, nums []int) []int {
n := len(parents)
g := make([][]int, n)
for w := 1; w < n; w++ {
v := parents[w]
g[v] = append(g[v], w)
}
mex := make([]int, n)
var f func(int) map[int]bool
f = func(v int) map[int]bool {
inSet := map[int]bool{}
mex[v] = 1
for _, w := range g[v] {
s := f(w)
// 启发式合并:保证从小的集合合并到大的集合
if len(s) > len(inSet) {
inSet, s = s, inSet
}
for x := range s {
inSet[x] = true
}
if mex[w] > mex[v] {
mex[v] = mex[w]
}
}
inSet[nums[v]] = true
for inSet[mex[v]] {
mex[v]++ // 不断自增直至 mex[v] 不在集合中
}
return inSet
}
f(0)
return mex
}
思路四:利用无重复基因值的性质
由于没有重复基因,若存在一个节点 x,其基因值为 1,那么从 x 到根这一条链上的所有节点,由于子树包含 x,其
均大于 1,而其余不在链上的节点,由于子树不包含 x,故其
均为 1。因此,我们只需要计算在这条链上的节点的
值。
我们可以从 x 出发,顺着父节点往根走,同时收集当前子树下的所有基因值,然后再不断自增子树的
直至其不在基因值集合中。
时间复杂度:
。
func smallestMissingValueSubtree(parents []int, nums []int) []int {
n := len(parents)
mex := make([]int, n)
for i := range mex {
mex[i] = 1
}
g := make([][]int, n)
for w := 1; w < n; w++ {
v := parents[w]
g[v] = append(g[v], w)
}
inSet := map[int]bool{}
var f func(int)
f = func(v int) {
inSet[nums[v]] = true // 收集基因值
for _, w := range g[v] {
if !inSet[nums[w]] { // 避免重复访问节点
f(w)
}
}
}
// 找到基因值等于 1 的节点 x
x := -1
for i, v := range nums {
if v == 1 {
x = i
break
}
}
// x 顺着父节点往上走
for cur := 2; x >= 0; x = parents[x] {
f(x)
for inSet[cur] {
cur++ // 不断自增直至不在基因值集合中
}
mex[x] = cur
}
return mex
}
[1]
力扣 - 每棵子树内缺失的最小基因值: https://leetcode-cn.com/problems/smallest-missing-genetic-value-in-each-subtree/
[2]
大佬的分析: https://leetcode-cn.com/problems/smallest-missing-genetic-value-in-each-subtree/solution/er-cha-shu-xian-xu-bian-li-gen-zuo-you-g-8c0m/
[3]
大佬的视频: https://www.bilibili.com/video/BV15f4y1P7XP?p=5
[4]
巨佬的go语言题解: https://leetcode-cn.com/problems/smallest-missing-genetic-value-in-each-subtree/solution/go-qi-fa-shi-he-bing-by-endlesscheng-kmff/
[5]
证明: https://oi-wiki.org/graph/dsu-on-tree/#_3