分析
首先看下数据量,总共元素有10万个,值最大为100万。时间复杂度应该控制在O(n.logn)或者O(n)。
本题可以使用平衡树O(n.logn)、并查集O(n+m)来进行解决。
并查集思路:普通并查集主要是查找一个范围中的代表元素,是树型的,而在本题中可以转换为单链表型,实际代码并没有多大的改动,主要是思路上。
核心思想:对于并查集数组中通过对应数组位置的元素值应当存入下一个要找的点的值。
初始状态:
使用单链表并查集后状态:
实际上就是做一个find查询找到没有访问过的数,然后我们来进行一个手动赋值操作。
题解:单链表式并查集
复杂度分析:时间复杂度O(n + m);空间复杂度O(n + m)
import java.util.*;
import java.io.*;
class Main {
static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
//最大情况就是Ai的最大值向后偏移10万数据
static final int N = 1100010;
static int n;
//并查集
static int[] p = new int[N];
//存储读入数组
// static int[] a = new int[N];
//并查集查询下一个节点
public static int find(int num) {
if (num != p[num])
p[num] = find(p[num]); //路径压缩
return p[num];
}
public static void main(String[] args) throws Exception{
n = Integer.parseInt(cin.readLine());
//初始化并查集
for (int i = 0; i < N; i ++) {
p[i] = i;
}
//读入数据
String[] ss = cin.readLine().split(" ");
for (int i = 0; i < n; i ++) {
int num = Integer.parseInt(ss[i]);
//查找最近元素
int findNum = find(num);
System.out.printf("%d ", findNum);
p[findNum] = findNum + 1;
}
}
}
Orz