945. 使数组唯一的最小增量

#945. 使数组唯一的最小增量

题目描述

解题思路
1、先排序再遍历：
先对数组进行排序，自带的排序就可以的。最小的元素肯定是不需要增量的，然后遍历数组比较大小，如果后一个数字与前一个相等，就把后面那个数字加一。这样加一后会造成就是已经排好序的数组，但是后面元素比前一个小，所以判断条件的时候要增加：如果A[i] <= A[i-1]，那么后一个元素等于前一个元素加一 ，不能直接加一，否则无法达到要求，会出现相邻两个数字相等。

 public int minIncrementForUnique(int[] A) {        
 	Arrays.sort(A);         
 	int move = 0;         
 	//遍历数组，第一个元素最小是不需要增量的，如果当前元素小于前一个元素，则等于前一个元素加一         
 	for (int i = 1; i < A.length; i++) {            
	 	if(A[i] <= A[i-1]) {                
	 	move += A[i-1] + 1 - A[i];                
	 	A[i] = A[i-1] + 1;            
	 	}        
	 }         
 	return move;    
 }

先排序再遍历的方法，时间复杂度 O(nlogn)
结果：

2、先计数再遍历O(N)
第一种方法主要时间复杂度在于排序，也可以不进行排序，先计数再遍历。因为题目里面给了范围限制，数组长度小于40000且每个数字也小于40000，所以可以直接用数组作为底层数据结构。在计数的时候得到max，可以减少后面的循环次数。

public int minIncrementForUnique(int[] A) {        
	int count[] = new int[400001];         
	int move = 0,max = -1,d = 0;         
	for (int a : A) {                
		count[a]++; // 计数                
		max = Math.max(max, a); // 计算数组中的最大值            
	}         
	for (int i = 0; i <= max ; i++) {            
		if (count[i] > 1) {                
		d = count[i] - 1; //需要移动的数量                
		count[i+1] += d; //暂时移动到下一位                
		move += d; //移动次数增加                            
		}        
	}            
	//最后max的那位要移动的次数应该是累乘得到的，例如最大值有5个，应该移动（1+2+3+4）=n*(n+1)/2次         
	// 最后, counter[max+1]里可能会有从counter[max]后移过来的，counter[max+1]里只留下1个，其它的d个后移。        
	d = count[max+1] - 1;        
	move += d*(d+1)/2;         
	return move;    
}

这种方法效果比前一种更好：

3、线性探测法O(N) （含路径压缩）
看的评论里面的题解，感觉好巧妙啊，大神真厉害。

这道题换句话说，就是需要把原数组映射到一个地址不冲突的区域，映射后的地址不小于原数组对应的元素。
比如[3, 2, 1, 2, 1, 7]就映射成了[3, 2, 1, 4, 5, 7]。
我想了下，这道题目其实和解决hash冲突的线性探测法比较相似！
如果地址冲突了，会探测它的下一个位置，如果下一个位置还是冲突，继续向后看，直到第一个不冲突的位置为止。
关键点：因为直接线性探测可能会由于冲突导致反复探测耗时太长，因此我们可以考虑探测的过程中进行路径压缩。
怎么路径压缩呢？就是经过某条路径最终探测到一个空位置x后，将这条路径上的值都变成空位置所在的下标x，那么假如下次探测的点又是这条路径上的点，则可以直接跳转到这次探测到的空位置x，从x开始继续探测。
下面用样例2：[3, 2, 1, 2,1, 7]，来模拟一遍线性探测的过程.


代码实现：

class Solution {    
int pos[] = new int[80000];    
public int minIncrementForUnique(int[] A) {        
	Arrays.fill(pos,-1);  //-1表示这个位置为空         
	int move = 0;    
	// 遍历每个数字a对其寻地址得到位置b, b比a的增量就是操作数。        
	for (int a : A) {            
		move += findPos(a) - a;        
	}        
	return move;    
}    
public int findPos(int x) {        
	if (pos[x] == -1) { //如果当前位置为空，直接放入数组            
		pos[x] = x;            
		return x;    
	}        
	else {      //否则向后寻址            
		int i = x+1;            
		while (pos[i] != -1) {            
			i++;        
		}               
	 	pos[x]  = pos[i] = i;        
	 	return i;    
	 	}    
	 }
}

这种方法提交的时候效率不太高，还不知道为什么，题解里面有用递归方式，代码如下：

// 线性探测寻址（含路径压缩）    
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;    
}