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

查重类题目，想到用标记数组记录是否出现过
但是最坏情况下可能会从头找到小尾巴，时间复杂度O(n²)，数据范围10⁶显然超时
再细看下题目，我们重复进行了寻找是否出现过，干脆把每个元素出现过的次数k记录下来，直接跳到后k个位置，实现O(n)

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
const int maxN = 1100005;
int h[maxN];
int main(){
	int n, t, l, r, m, temp;
	vector<int> vi;
	memset(h, 0, sizeof(h));
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%d", &t);
		while(h[t] != 0) {
			temp = t;
			t += h[t];
			h[temp]++;
		}
		h[t] = 1;
		vi.push_back(t);
	}
	for(int i = 0; i < vi.size(); i++)
		printf("%d ", vi[i]);
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25