链接
https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/
耗时
解题:48 min
题解:26 min
题意
给定一个整数数组 A,现只有一个操作:将 A[i] 自加 1。问使 A 中的每个值都是唯一的最少操作次数。
思路
若要使 A 中的每个值唯一,那么直观上最少的操作次数一定是尽可能利用原本的数组,加尽可能少的 1,并且使得到的结果是,任意大小相邻的两个数之间的差尽可能的小。
为使大小相邻的两个数之间的差尽可能的小,那么就按顺序进行加 1 操作,如果从大到小操作可能会出现回退的情况,所以从小到大进行加 1 操作。
将数组 A 从小到大排序,然后顺序遍历,若
A
[
i
]
+
1
≤
A
[
i
+
1
]
A[i]+1 \leq A[i+1]
A[i]+1≤A[i+1] 说明 A[i] 和 A[i+1] 唯一,无需操作,若
A
[
i
]
+
1
>
A
[
i
+
1
]
A[i]+1 > A[i+1]
A[i]+1>A[i+1] 说明两数相等或者之前进行过加 1 操作,那么为了实现唯一,A[i+1] 至少要变成 A[i]+1,即进行 A[i]+1-A[i+1] 次加 1 操作。时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)(排序复杂度)。
AC代码
class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
sort(A.begin(), A.end());
int ans = 0;
int n = A.size();
for(int i = 0; i < n-1; ++i) {
if(A[i]+1 > A[i+1]) {
ans += A[i]+1-A[i+1];
A[i+1] = A[i]+1;
}
}
return ans;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)