題目來源:https://leetcode.com/contest/weekly-contest-112/problems/minimum-increment-to-make-array-unique/
問題描述
945. Minimum Increment to Make Array Unique
Given an array of integers A, a move consists of choosing any
A[i]
, and incrementing it by
1
.
Return the least number of moves to make every value in
A
unique.
Example 1:
Input: [1,2,2]
Output: 1
Explanation: After 1 move, the array could be [1, 2, 3].
Example 2:
Input: [3,2,1,2,1,7]
Output: 6
Explanation: After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.
Note:
-
0 <= A.length <= 40000
-
0 <= A[i] < 40000
------------------------------------------------------------
題意
給出一個數列,每次将數列的一個元素+1稱為一次“操作”。求使數列中元素互不相同的最小操作次數。
------------------------------------------------------------
思路
首先将數組排序。用cur記錄數列中前一項,操作直到該項比前一項多1。如果有多個數字重複,則cur表示已經加過若幹個1的前項。
------------------------------------------------------------
代碼
class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
if (A.empty())
{
return 0;
}
sort(A.begin(), A.end());
int i, n = A.size(), cur = A[0], addi, ret = 0;
for (i=1; i<n; i++)
{
addi = (cur + 1 - A[i]) > 0 ? (cur + 1 - A[i]) : 0;
ret += addi;
cur = A[i] + addi;
}
return ret;
}
};