05 August 2008
通过对元素+1，让整数数组里的每个元素都是unique，求最少increment数
方法一、排序 O(nlogn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int minIncrementForUnique(int[] nums) {
// 先排序
Arrays.sort(nums);
int move = 0;
// 遍历数组，若当前元素小于等于它的前一个元素，则将其变为前一个数+1
for (int i = 1; i < nums.length; i++) {
if (nums[i] <= nums[i - 1]) {
int pre = nums[i];
nums[i] = nums[i - 1] + 1;
move += nums[i] - pre;
}
}
return move;
}
}
方法二、counting sort 计数排序 O(N)
(下面代码有的极端cases不能过)
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
26
27
28
class Solution {
public int minIncrementForUnique(int[] nums) {
// counter数组统计每个数字的个数。
//（这里为了防止下面遍历counter的时候每次都走到40000，所以设置了一个max，这个数据量不设也行，再额外设置min也行）
int[] counter = new int[40001];
int max = -1;
for (int num: nums) {
counter[num]++;
max = Math.max(max, num);
}
// 遍历counter数组，若当前数字的个数cnt大于1个，则只留下1个，其他的cnt-1个后移
int move = 0;
for (int num = 0; num <= max; num++) {
if (counter[num] > 1) {
int d = counter[num] - 1;
move += d;
counter[num + 1] += d;
}
}
// 最后, counter[max+1]里可能会有从counter[max]后移过来的，counter[max+1]里只留下1个，其它的d个后移。
// 设 max+1 = x，那么后面的d个数就是[x+1,x+2,x+3,...,x+d],
// 因此操作次数是[1,2,3,...,d],用求和公式求和。
int d = counter[max + 1] - 1;
move += (1 + d) * d / 2;
return move;
}
}
方法三、线性探测法 O(N) （含路径压缩） 这道题换句话说，就是需要把原数组映射到一个地址不冲突的区域，映射后的地址不小于原数组对应的元素。
比如 [3, 2, 1, 2, 1, 7] 就映射成了 [3, 2, 1, 4, 5, 7]。
其实和解决 hash 冲突的线性探测法比较相似！(下面代码有的极端cases不能过)
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
26
27
28
29
class Solution {
int[] pos = new int[80000];
public int minIncrementForUnique(int[] nums) {
Arrays.fill(pos, -1); // -1表示空位
int move = 0;
// 遍历每个数字a对其寻地址得到位置b, b比a的增量就是操作数。
for (int a : nums) {
int b = findPos(a);
move += b - a;
}
return move;
}
// 线性探测寻址（含路径压缩）
private int findPos(int a) {
int b = pos[a];
// 如果a对应的位置pos[a]是空位，直接放入即可。
if (b == -1) {
pos[a] = a;
return a;
}
// 否则向后寻址
// 因为pos[a]中标记了上次寻址得到的空位，因此从pos[a]+1开始寻址就行了（不需要从a+1开始）。
b = findPos(b + 1);
pos[a] = b; // 寻址后的新空位要重新赋值给pos[a]哦，路径压缩就是体现在这里。
return b;
}
}