資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告