[蓝桥杯 2019 省 A] 修改数组-EW帮帮网

一.题目

题目描述

给定一个长度为 N 的数组 $A=[A_,A_2,⋅⋅⋅A_N]$ ，数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。

小明会依次修改 $A_,A_2,⋅⋅⋅A_N$ 。

当修改 $A_i$ 时，小明会检查 $A_i$ 是否在 $A_1∼A_{i−1}$ 中出现过。

如果出现过，则小明会给 $A_i$ 加上 1；如果新的 $A_i$ 仍在之前出现过，小明会持续给 $A_i$ 加 1，直到 $A_i$ 没有在 $A_1∼A_{i−1}$ 中出现过。

当 $A_N$ 也经过上述修改之后，显然 A 数组中就没有重复的整数了。

现在给定初始的 A 数组，请你计算出最终的 A 数组。

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 $A_1,A_2,⋅⋅⋅,A_N$ 。

输出格式

输出 N 个整数，依次是最终的 $A_1,A_2,⋅⋅⋅,A_N$ 。

数据范围

1 ≤ N ≤ 10⁵,
1 ≤ $A_i$ ≤10⁶

输入样例

5
2 1 1 3 4

输出样例

2 1 3 4 5

二.解释

看完题目，我首先想到的是直接模拟过程，不过这只能解部分样例。既然模拟复杂度太高，自然要优化一下，从哪里入手呢。

在模拟中复杂度最高的是找一个不在之前序列出现过的最小的数，那么我们可以直接用一个集合记录当前所有可用的数，使用二分查找找到大于等于目标的数。

三.代码

1.直接模拟:

#include <iostream>
#include <unordered_map>

using namespace std;

const int MaxN = 1e5 + 10;

int InN;						//数据个数
int Ns[MaxN];					//保存序列
unordered_map<int, int> Map;	//保存已经使用的数

int main()
{
	cin >> InN;
	for(int i = 1; i <= InN; i++)
	{
		scanf("%d", Ns + i);
		while(Map.count(Ns[i]))	//这里是复杂度最高的部分
		{
			Ns[i]++;
		}
		Map[Ns[i]]++;
		Res[Count++] = Ns[i];
	}
	
	for(int i = 1; i <= InN; i++) { printf("%d ", Ns[i]); }
	
	return 0;	
}

2.优化：

#include <iostream>
#include <unordered_map>
#include <set>

using namespace std;

const int MaxN = 1e5 + 10;

int InN;			//数据个数
set<int> Ns;		//记录当前所有可用的数
int Res[MaxN];		//保存结果

int main()
{
	cin >> InN;
	for (int i = 1; i <= 1e5 + 1e6; i++) { Ns.insert(i); }	//预处理到1e5 + 1e6是为了防止越界

	int a;
	for (int i = 1; i <= InN; i++)
	{
		scanf("%d", &a);
		Res[i] = *Ns.lower_bound(a);	//这里直接使用lower_bound，在集合中找一个大于等于a的数
		Ns.erase(Res[i]);				//删除使用过的数
	}

	for (int i = 1; i <= InN; i++) { printf("%d ", Res[i]); }

	return 0;
}

[蓝桥杯 2019 省 A] 修改数组