数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中使数组唯一所需的最小增量
假设我们有一个整数数组 A，这里一次移动包括选择任何 A[i] 并将其加 1。我们必须找到使 A 中每个值都唯一的最小移动次数。因此，如果输入类似于 [3,2,1,2,1,7]，则输出将为 6，因为在 6 次移动后，数组可以是 [3,4,1,2,5,7]，可以证明用 5 次或更少的移动次数不可能使数组具有所有不同的值。
为了解决这个问题，我们将遵循以下步骤 -
ret:= 0
对数组 A 进行排序
创建一个名为 visited 的集合来跟踪之前考虑过哪些值
对于 i 从 1 到数组 A 的大小 - 1
如果 A[i] < A[i – 1]，则 ret := ret + (1 + A[i – 1 ]) – A[i]，并且 A[i] := A[i – 1] + 1
返回 ret。
让我们看看以下实现以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
int ret = 0;
sort(A.begin(), A.end());
set <int> visited;
for(int i = 1; i < A.size(); i++){
if(A[i] <= A[i - 1]){
ret+= (A[i - 1] + 1) - A[i];
A[i] = A[i - 1] + 1;
}
}
return ret;
}
};
main(){
vector<int> v1 = {3,2,1,2,1,7};
Solution ob;
cout << (ob.minIncrementForUnique(v1));
}输入
[3,2,1,2,1,7]
输出
6
更新于: 2020 年 4 月 30 日
287 次浏览
广告