題目：使陣列唯一的最小增量
給定整數陣列 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
思路很簡單，將這一陣列從小到大排序，然后在對每個數進行操作就可以了，
直接上代碼（c）：
int cmp( const void *a, const void *b ) { return *( int *)a - *( int *)b; } int minIncrementForUnique(int* A, int ASize){ int ans = 0; qsort( A, ASize, sizeof(A[0]), cmp ); for( int i = 1; i < ASize; i++ ) { while( A[i] <= A[i-1] ) { A[i]++; ans++; } } return ans; }
由于這個方法是對每個數一步一步的增加的，所以當數字非常大的時候，耗時十分恐怖，最終結果：
其實不必一步一步來，要使陣列唯一，move操作最少，那么每個數只需要比上一個數大1就可以了，
可以通過兩個數的關系直接計算，
上代碼（c）：
int cmp( const void *a, const void *b ) { return *( int *)a - *( int *)b; } int minIncrementForUnique(int* A, int ASize){ int ans = 0; qsort( A, ASize, sizeof(A[0]), cmp ); for( int i = 1; i < ASize; i++ ) { if( A[i] <= A[i-1] ) { ans += A[i-1]-A[i]+1; A[i] = A[i-1]+1; } } return ans; }
最終結果：
舒服多了~
2020-03-22-10:59:24
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/43033.html
標籤：C
上一篇：指標陣列與陣列指標
下一篇：開機方案題解