思路

这道题他是求在对于 $i$ 最少需要修改多少次才能使 $0$ 到 $i$ 中不包含的最小非负整数为 $i$。

对于 $i$ 我们要求不包含的最小非负整数，自然就要知道 $i$ 之前不包含的最小非负整数的个数。如果对于 $i$ 我们再去循环 $0$ 到 $i - 1$ 统计数量的话，那么复杂度就会变成 $O(n^2)$，看一看数据范围 $1 \le N \le 2 \times 10^5$ 不用说肯定炸烂掉。

那怎么办呢？我们可以定义一个 $cnt$ 变量在枚举 $i$ 时来统计 $i$ 之前不包含的最小非负整数的个数。在统计之前需要将输入的数进行一个整合，就是计算每个数的数量，当这个数的数量为 $0$ 时，$cnt$ 增加 $1$，也就是 cnt++;。

接下来就是判断至少需要修改多少次。经过观察我们可以发现：

1. 当 $cnt$ 为 $0$ 时，说明 $i$ 之前没有不包含的最小非负整数。这时如果 $i$ 的数量为 $0$，那么 $i$ 为不包含的最小非负整数，修改次数就为 $0$ 次。

2. 当 $cnt$ 为 $0$ 时，如果 $i$ 的数量不为 $0$，意味这 $i$ 为包含的非负整数，要令不包含的最小非负整数为 $i$，就需要把所有的 $i$ 修改为不为 $i$ 的值，修改次数就为 $i$ 的个数。

3. 当 $cnt$ 不为 $0$ 时，说明 $i$ 之前有不包含的最小非负整数。就需要把这 $cnt$ 个数各用一个数代替，如果 $i$ 这个数的个数小于等于 $cnt$ 时，我们就可以用所有的 $i$ 和其他有多余的数进行修改，直到刚好将这 $cnt$ 个数都代替，修改次数就为 $cnt$。

4. 当 $cnt$ 不为 $0$ 时，且 $i$ 这个数的个数大于 $cnt$ 时，我们就可以用所有的 $i$ 进行修改，直到刚好将这 $cnt$ 个数都代替，剩余的部分全部修改不为 $i$ 数，修改次数为 $i$ 的个数。

剩下的就可以交给代码实现了。

代码

时间复杂度：$O(n)$

#include <iostream>

using namespace std;

const int N = 2e5 + 10;
int a[N];

int main()
{
	int n;
	cin >> n;
	for(int i = 1;i <= n; ++ i)
	{
		int x;
		cin >> x;
		a[x] ++; //计算每个相同的数的数量
	}
	
	long long cnt = 0;
	
	for(int i = 0;i <= n; ++ i)
	{
		if(cnt > a[i])
			cout << cnt << endl;
		else cout << a[i] << endl;
//------------------------------------------------
//计算i之前不包含的最小非负整数的个数
		if(a[i] == 0)
			cnt ++;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(False);
    cin.tie(Noneptr);

    int N; cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    // cnt[i] = # of times the number `i` appears in A
    vector<int> cnt(N+1);
    for (int x : A) {
        cnt[x]++;
    }

    // missing_lt_i = how many numbers in [0..i) are missing from A?
    int missing_lt_i = 0;

    for (int i = 0; i <= N; i++) {
        cout << max(cnt[i], missing_lt_i) << "\n";
        bool is_i_missing_from_A = cnt[i] == 0;
        if (is_i_missing_from_A) {
            missing_lt_i++;
        }
    }
}