题目描述

难度分:$1500$

输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq n)$。

最少要修改多少个元素，使得$a$是一个$1$~$n$的排列？

输出最少修改次数，以及修改后的$a$。

如果有多个$a$符合要求，输出字典序最小的$a$。

输入样例$1$

4
3 2 2 3

输出样例$1$

2
1 2 4 3 

输入样例$2$

6
4 5 6 3 2 1

输出样例$2$

0
4 5 6 3 2 1 

输入样例$3$

10
6 8 4 6 7 1 6 3 4 5

输出样例$3$

3
2 8 4 6 7 1 9 3 10 5 

算法

贪心

这个题的第一要义是操作次数少，因此我们用一个数组$cnt$统计一下$a$中每个数值的频数，对于数值$val$，如果它的频数$freq=cnt[val]$超过$1$，那么有$freq-1$个$val$就都是要改成其他数的，因此操作次数就是$freq$大于$1$的所有$freq-1$之和（同样也是$[1,n]$内缺少的那些数的个数）。

接下来贪心地来进行替换，先将$[1,n]$中所有缺少的数存入$not\_used$数组（保持有序），然后遍历原数组$a$，对于$a[i]$，替换与否分以下三种情况来讨论：

1. 如果$a[i]$的频数超过$1$，那显然$a[i]$是有可能被替换的，此时如果$not\_used$中的最小数小于$a[i]$，那就果断用这个最小数将$a[i]$替换掉，并更新$a[i]$的频数（自减）。
2. 如果$a[i]$已经出现过了（这里可以用一个$used$数组来标记每个数是否出现过），此时也需要用$not\_used$中的最小数把$a[i]$替换掉。
3. 否则不替换，$a[i]$仍然保持原值。

复杂度分析

时间复杂度

统计各个数值的频数，构建$not\_used$数组都需要遍历一遍$a$数组，时间复杂度为$O(n)$。接下来贪心地替换$a[i]$也是遍历$i \in [1,n]$，由于可以让$not\_used$数组保持有序，能够在$O(1)$的时间复杂度下获得最小值，时间复杂度仍然为$O(n)$。因此，算法整体的时间复杂度为$O(n)$。

空间复杂度

空间瓶颈在于频数数组$cnt$和$not\_used$数组，都是$O(n)$规模的，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 200010;
int n, a[N], cnt[N], used[N];

int main() {
    scanf("%d", &n);
    memset(cnt, 0, sizeof cnt);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        cnt[a[i]]++;
    }
    memset(used, 0, sizeof used);
    vector<int> not_used;
    for(int i = 1; i <= n; i++) {
        if(!cnt[i]) not_used.push_back(i);
    }
    printf("%d\n", (int)not_used.size());
    int j = 0;
    for(int i = 1; i <= n; i++) {
        if(cnt[a[i]] >= 2 && not_used[j] < a[i]) {
            int t = not_used[j];
            printf("%d ", not_used[j++]);
            cnt[a[i]]--;
            used[t]++;
        }else if(used[a[i]]) {
            used[not_used[j]]++;
            printf("%d ", not_used[j++]);
        }else {
            used[a[i]]++;
            printf("%d ", a[i]);
        }
    }
    return 0;
}