214场LeetCode周赛后，偶然看到了T2用并查集解决此类问题的解法，故在此总结一下

例题1.修改数组

• 链接：AcWing1242.调整数组

思路

• 维护一个并查集，枚举到第i个元素的时候，使得并查集的根节点存储的是刚好能放置的最小数字
• 感觉不太好形容，直接模拟一个样例体会一下

数组：[2,1,1,3,4]
初始化并查集，使每个数的根节点都是自己

枚举到2，根节点为自己，表示第一次出现，把2连到3上，表示再枚举到2的时候需要调整为3
枚举到1，根节点为自己，表示第一次出现，把1连到2上，此时1,2都合并到3，表示再枚举到1或者2的时候需要调整为3
枚举到1，根节点为3，表示需要调整为3，并且把1所在集合合并到4上，表示再出现1到3之间的数需要调整为4
枚举到3，根节点为4，表示需要调整为4，并且把3所在集合合并到5上，表示再出现1到4之间的数需要调整为5
枚举到4，根节点为5，表示需要调整为5，并且把4所在集合合并到6上，表示再出现1到5之间的数需要调整为6

所以答案为[2,1,3,4,5]

Java代码

import java.util.*;

public class Main{
    static int[] p = new int[1000010];
    static int find(int x){
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0; i < 1000010; i++) p[i] = i;
        for(int i = 0; i < n; i++){
            int x = sc.nextInt();
            int t = find(x);
            System.out.print(t + " ");
            p[t] = t+1;
        }
    }
}

例题2.

• 链接：214场周赛.T2.字符频次唯一的最小删除次数

思路

• 上一个题是遇到重复元素调整元素使得元素变大，这个题是遇到重复元素（字母的出现频次）调整元素使得元素变小，且最小只能变成0，即删除该字符，其实就相当于上一个题的对偶问题
• 需要注意的是，如果集合与0合并，则说明该元素需要全部删除才能保证没有重复元素出现

模拟：s = "ceabaacb"
统计字符频次，发现c有2个，e有1个，b有2个，a有3个，则频次数组为[2,1,2,3]

枚举2，合并2和1，说明如果发生重复，后面还能放的最大数为1
枚举1，合并1和0，说明如果发生重复，后面还能放的最大数为0
枚举2，发现根节点为0，全部删除，即元素2给答案的贡献为2
枚举3，合并3和集合(1,2)，则说明再出现1,2,3需要全部删除

Java代码

class Solution {
    int[] p = new int[100010];
    int find(int x){
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }

    public int minDeletions(String s) {
        int[] hash = new int[26];
        for(char c: s.toCharArray()) hash[c-'a']++;
        for(int i = 0; i <= s.length(); i++) p[i] = i;

        int res = 0;
        for(int cnt: hash){
            if(cnt == 0) continue;
            int t = find(cnt);
            res += cnt - t;
            p[t] = Math.max(0, p[t]-1);
        }
        return res;
    }
}