蓝桥杯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;
}