算法分析
并查集
将前面枚举过的元素用一个集合来表示,集合的根元素是集合所有元素的最大值
时间复杂度 $O(n)$
Java 代码
import java.util.Scanner;
public class Main{
static int N = 1000010;
static int[] p = new int[N];
static int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 0;i <= 1000000;i ++) p[i] = i;
for(int i = 0;i < n;i ++)
{
int x = scan.nextInt();
x = find(x);
System.out.print(x + " ");
p[x] = x + 1;
}
}
}
orz感谢大佬的思路!!!!