欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-24 16:28:30
...

#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)
结果:
945. 使数组唯一的最小增量
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;    
}

这种方法效果比前一种更好:
945. 使数组唯一的最小增量
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],来模拟一遍线性探测的过程.
945. 使数组唯一的最小增量945. 使数组唯一的最小增量
945. 使数组唯一的最小增量
代码实现:

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;    
	 	}    
	 }
}

945. 使数组唯一的最小增量
这种方法提交的时候效率不太高,还不知道为什么,题解里面有用递归方式,代码如下:

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

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

相关标签: 力扣刷题笔记