ISSAC

用户名：uq_50089742160

访问量：5766

签　名：

等　　级
排　　名	705
经　　验	3912
参赛次数	8
文章发表	8
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯历届试题-网络寻路-题解（C++代码）
浏览：377

信息学奥赛一本通T1311-求逆序对-题解（C++代码）
浏览：2067

你可能喜欢

蓝桥杯2019年第十届真题-修改数组-题解(C++代码)

　　作者: ISSAC　　　　发表时间：2020-03-29 12:14:19 浏览：1119　|　评论：1　

原题链接：蓝桥杯2019年第十届省赛真题-修改数组

#问题 2301: [蓝桥杯][2019年第十届真题]修改数组

时间限制: 1Sec 内存限制: 128MB 提交: 234 解决: 36

题目描述
给定一个长度为 N 的数组 A = [A1, A2, · · · AN ]，数组中有可能有重复出现 的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 A2,A3,··· ,AN。

当修改 Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。如果出现过，则 小明会给 Ai 加上 1 ;如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直 到 Ai 没有在 A1 ∼ Ai−1 中出现过。

当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。 现在给定初始的 A 数组，请你计算出最终的 A 数组

输入
第一行包含一个整数 N。 第二行包含N个整数A1,A2,··· ,AN

输出
输出N个整数，依次是最终的A1,A2,··· ,AN。

样例输入
5
2 1 1 3 4
样例输出
2 1 3 4 5
提示

对于 80% 的评测用例，1 ≤ N ≤ 10000。

对于所有评测用例，1 ≤ N ≤ 100000，1 ≤ Ai ≤ 1000000。

分析：这道题就是查重类题目，我们可以这样想，我们定义一个访问数组visited，开始都设置为0，表示未被访问的状态。如果当输入一个数x，若没被访问，则直接保存，并将visited【x】设置为1，如果x已经被访问则将x=x+1，直到visited【x】没有被访问，然后保存进数组。这样做有一个缺点。如果输入的整个数组都是一样的数，则会有最坏的时间复杂度即O(n^2)，有兴趣的同学自己证明，这样时间就容易超限，于是我们需要进行优化，下面先展示未优化的代码，大约时间超限17%。

```cpp
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
int A[100005];
int n;
int visited[1000055];
void set()
{
	for(int i=0;i<100005;i++)
	A[i]=0;
	for(int i=0;i<1000055;i++)
	visited[i]=0;
}
int main()
{
	set();
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		while(visited[x]!=0)
		{   
		   x+=1;
		}
		A[i]=x;
		visited[x]=1;
	}
	for(int i=0;i<n;i++)
	{
		printf("%d ",A[i]);
	}
		return 0;
}
```

下面提供优化代码，当我们仔细研究时发现，我们其实可以去掉多余的访问，例如一个数已经被访问了k次，那么就说明他后面的k个数一定都被访问了，所以我们可以将访问数组visited改为记录访问次数的数组。例如，当visited【x】=k时，正好输入的数是x，则我们直接将x跳到x+k的位置再进行判断是否被访问。
这样未优化代码的最坏的情况时间复杂度直接变成了O（n）。

代码：

```cpp
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
int A[100005];
int n;
int visited[1000055];
void set()
{
	for(int i=0;i<100005;i++)
	A[i]=0;
	for(int i=0;i<1000055;i++)
	visited[i]=0;
}
int main()
{
	set();
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		while(visited[x]!=0)
		{   
		   visited[x]++;
		   x+=(visited[x]-1);
		}
		A[i]=x;
		visited[x]++;
	}
	for(int i=0;i<n;i++)
	{
		printf("%d ",A[i]);
	}
		return 0;
}
```

0.0分

12 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

星空皓月

2021-03-03 21:05:09

ISSAC

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

简单编码（C++代码）（这里推荐用switch）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

简单的a+b （C语言代码）

蓝桥杯2019年第十届真题-修改数组-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

ASCII帮了大忙

A+B for Input-Output Practice (III) （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

C语言训练-亲密数（C语言代码）

矩阵乘方（C语言代码）

ISSAC

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

简单编码 （C++代码）（这里推荐用switch）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

简单的a+b （C语言代码）

蓝桥杯2019年第十届真题-修改数组-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

ASCII帮了大忙

A+B for Input-Output Practice (III) （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

C语言训练-亲密数 （C语言代码）

矩阵乘方 （C语言代码）

简单编码（C++代码）（这里推荐用switch）

　　评论区

C语言训练-亲密数（C语言代码）

矩阵乘方（C语言代码）