我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii LeetCode 945. 使數組唯一的最小增量題目給定整數數組 A，每次 move 操作將會選擇任意 A[i]，並將其遞增 1。返回使 A 中的每個值都是唯一的最少 ...

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 945. 使數組唯一的最小增量

題目

給定整數數組 A，每次 move 操作將會選擇任意 A[i]，並將其遞增 1。

返回使 A 中的每個值都是唯一的最少操作次數。

示例 1:

輸入：[1,2,2]
輸出：1
解釋：經過一次 move 操作，數組將變為 [1, 2, 3]。
示例 2:

輸入：[3,2,1,2,1,7]
輸出：6
解釋：經過 6 次 move 操作，數組將變為 [3, 4, 1, 2, 5, 7]。

可以看出 5 次或 5 次以下的 move 操作是不能讓數組的每個值唯一的。

提示：

0 <= A.length <= 40000
0 <= A[i] < 40000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

思路1-先排序，再從左向右累加每兩個臨近數需要的+1操作數；

Arrays.sort(A)排序；
順次比較並記錄將後一個數變為前一個數+1數所需要的操作數；

例子：假如排序後是1123455那麼從第二個數開始：

第一次：1223455 此時move+=2-1
第二次：1233455 此時move+=3-2
第三次：1234455 此時move+=4-3
第四次：1234555 無需操作
第五次：1234565 此時move+=6-5
第六次：1234567 此時move+=7-6
其中：
時間複雜度：O(NlogN) N=A.length
空間複雜度：O(1)

思路2-先統計順次進行操作數的累加，每次需要累加+1操作的次數是相同數的個數；

創建新數組new int[40001]，然後將A中每個數作為下標進行統計；
遍歷新數組，1中統計到的相同數大於0的，其-1後的數就是這些數需要進行+1操作的數，並把這些+1操作後的數累加給下一個統計數，通過每次-1來使得最終數都不相同；
遍歷完後需要再檢查一下最大下標數的個數，若大於1，其中-1個數都需要進行+1操作，直接使用1-n的求和公式即可；

時間複雜度：O(N) N=max(A.length，max(A))
空間複雜度：O(40001)即O(1)

Tips:第一步的統計其實隱含了排序，利用了自然數的特性，下標天然有序是數組很容易被忽略的一個特性，比如字母（通過char的 -'a'操作）轉數組去統計就避免了額外排序；

思路3-路徑壓縮；（來自LeetCode評論區，很秀...）

創建新數組new int[80000]（初始化值-1），因為路徑壓縮不同於方法2中的統計（或者說是統計壓縮），這裡壓縮的是+1的操作，但是+1後的數需要新數組去記錄，若A中所有值都是39999，最後的最大數將是79999；
開始遍歷併進行路徑點位記錄findPath，這是個遞歸方法，可能比較繞，單獨分析下：

private int findPath(int i) {
	// 初次遇到點位，記錄值並返回，此時j=0
	if (path[i] == -1) {
		path[i] = i;
		return i;
	} else {
		// 若i有記錄，則向後找path[i] + 1位置的值，並最終遞歸更新路徑值
		path[i] = findPath(path[i] + 1);
		return path[i];
	}
}

對於例子：A{1，1，2，3，5，5，2｝，對應的路徑數組初始化的路徑值均為-1

0下標1的路徑值為-1，執行後更新為1並返回1，此時move+=1-1，對應1不需要+1操作;
1下標1的路徑值因為已經被標記為1了，所以往後找1+1的路徑值，此時找到的2的路徑值為-1，更新路徑1和2的值都為2並返回，最後move+=2-1，對應1需要1次+1操作；
2下標2的路徑值為2，往後找2+1的路徑值得到-1，此時將路徑1，2，3的路徑值都更新為3，最後move+=3-2，對應2需要1次+1操作；
3下標3的路徑值為3，往後找3+1的路徑值得到-1，此時將路徑1，2，3，4的路徑值都更新為4，最後move+=4-3，對應3需要1次+1操作；
4下標5的路徑值為-1，執行後更新為5並返回5，此時move+=5-5，對應5不需要+1操作;
5下標5的路徑值為5，往後找5+1的路徑值得到-1，此時將路徑1，2，3，4，5，6的路徑值都更新為6，最後move+=6-5，對應5需要1次+1操作；
6下標2的路徑值為6，往後找6+1的路徑值得到-1，此時將路徑1，2，3，4，5，6，7的路徑值都更新為7，最後move+=7-2，對應2需要5次+1操作；

所謂的路徑壓縮其實是記錄了當前已遍曆數經過+1操作後中的最大數，便於後面根據路徑直接找到最大數併在此基礎上計算需要+1的次數

演算法源碼示例

package leetcode;

import java.util.Arrays;

/**
 * @author ZhouJie
 * @date 2020年3月22日 下午8:04:55 
 * @Description: 945. 使數組唯一的最小增量
 *
 */
public class LeetCode_0945 {

}

class Solution_0945 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年3月22日 下午8:08:06 
	 * @param: @param A
	 * @param: @return
	 * @return: int
	 * @Description: 1-先排序，再從左向右累加每兩個臨近數需要的+1操作數；
	 * 				時間複雜度：O(NlogN) N=A.length
	 * 				空間複雜度：O(1)
	 *
	 */
	public int minIncrementForUnique_1(int[] A) {
		int len = 0, move = 0;
		if (A == null || (len = A.length) < 2) {
			return move;
		}
		Arrays.sort(A);
		for (int i = 1; i < len; i++) {
			// 若當前值小於等於前一個值，說明需要進行+1操作，+1操作的次數就等於差值再+1，此外還需要更新當前值為前一個值+1
			if (A[i] <= A[i - 1]) {
				move += A[i - 1] - A[i] + 1;
				A[i] = A[i - 1] + 1;
			}
		}
		return move;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年3月22日 下午8:15:17 
	 * @param: @param A
	 * @param: @return
	 * @return: int
	 * @Description: 2-先統計再由小到大進行操作數的累加，每次需要累加+1次數的是相同數的個數-1；
	 * 				其實統計這一步隱含了排序（自然數的特性），這也是比1方法快的關鍵原因
	 * 				時間複雜度：O(N) N=max(A.length，max(A))
	 * 				空間複雜度：O(40001)即O(1)
	 */
	public int minIncrementForUnique_2(int[] A) {
		int move = 0;
		if (A == null || A.length < 2) {
			return move;
		}
		// 因為最大數是3999，若+1為40000，需要用到40000索引
		int[] statistics = new int[40001];
		// 記錄最大數，用作遍歷statistics的右邊界
		int max = 0;
		for (int i : A) {
			statistics[i]++;
			max = Math.max(max, i);
		}
		max++;
		// max是A中最終可能的最大值
		for (int i = 0; i < max; i++) {
			// 若A中statistics[i]的個數大於1，說明statistics[i]-1個數需要進行+1操作，
			// 這一步只是給statistics[i]-1個數各進行了一次+1操作，後續的+1交給statistics[i+1]去完成（遞歸）
			if (statistics[i] > 1) {
				move += statistics[i] - 1;
				statistics[i + 1] += statistics[i] - 1;
			}
		}
		// 若statistics[max]的個數大於1，則statistics[max]-1個數（記為n個）需要進行+1操作；
		// 這n個數依次需要進行+1的次數為1、2、3、4....n，即對1-n求和，直接使用求和公式
		if (statistics[max] > 1) {
			int n = statistics[max] - 1;
			move += n * (n + 1) / 2;
		}
		return move;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年3月22日 下午8:36:13 
	 * @param: @param A
	 * @param: @return
	 * @return: int
	 * @Description: 1-路徑壓縮；（來自LeetCode評論區，很秀...）
	 * 				時間複雜度：O(N) N=A.length
	 * 				空間複雜度：O(80000)即O(1)
	 * 				因為findPath每次可能更改多個點位的值，所以效率沒有方法2高
	 */

	// 若A中所有數都相等且都為39999，則+1操作完成時，最大值將為79999
	int[] path = new int[80000];

	public int minIncrementForUnique_3(int[] A) {
		int move = 0;
		if (A == null || A.length < 2) {
			return move;
		}
		// -1為空地址標記，與A中數不同即可
		Arrays.fill(path, -1);
		for (int i : A) {
			int j = findPath(i);
			move += j - i;
		}
		return move;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年3月22日 下午8:49:55 
	 * @param: @param i
	 * @param: @return
	 * @return: int
	 * @Description: 路徑壓縮核心
	 *
	 */
	private int findPath(int i) {
		// 初次遇到點位，記錄值並返回，此時j=0
		if (path[i] == -1) {
			path[i] = i;
			return i;
		} else {
			// 若i有記錄，則向後找path[i] + 1位置的值，並最終遞歸更新路徑值
			path[i] = findPath(path[i] + 1);
			return path[i];
		}
	}
}