Problem
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 <= 400000 <= A[i] < 40000
Solution: Greedy
Sort the elements, make sure A[i] >= A[i-1] + 1, if not increase A[i] to A[i – 1] + 1
Time complexity: O(nlogn)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua, 56 ms class Solution { public: int minIncrementForUnique(vector<int>& A) { int ans = 0; sort(begin(A), end(A)); for (int i = 1; i < A.size(); ++i) { if (A[i] > A[i - 1]) continue; ans += (A[i - 1] - A[i]) + 1; A[i] = A[i - 1] + 1; } return ans; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 |
# Author: Huahua, Running time: 196 ms class Solution(object): def minIncrementForUnique(self, A): A.sort() ans = 0 for i in range(1, len(A)): if A[i] > A[i - 1]: continue ans += A[i - 1] - A[i] + 1 A[i] = A[i - 1] + 1 return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment