資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時裝設計
法律研究C++ 中的最小範圍 II
假設我們有一個整數陣列 A，對於每個整數 A[i]，我們必須選擇 x = -K 或 x = K，並將 x 新增到 A[i]（僅一次）。因此，在此過程之後，我們得到一個數組 B。我們必須找出 B 的最大值和 B 的最小值之間的最小可能差值。因此，如果輸入是 A = [0,10]，K = 2，那麼輸出為 6，因為 B = [2,8]。
為解決此問題，我們將遵循以下步驟 -
設定 ret := 0，n := 陣列 A 的大小
對陣列 A 進行排序
設定 ret := A 的最後一個元素 - A 的第一個元素
right := A 的最後一個元素 - K 和 left := A 的第一個元素 + k
對於 i 在 0 到 n - 1 之間的範圍
mx := A[i] + k 和 right 的最大值
mn := A[i + 1] - k 和 left 的最小值
ret := ret 和 (mx - min) 的最小值
返回 ret
讓我們看看以下實現以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int smallestRangeII(vector<int>& A, int k) {
int ret = 0;
int n = A.size();
sort(A.begin(), A.end());
ret = A[n - 1] - A[0];
int mx, mn;
int right = A[n - 1] - k;
int left = A[0] + k;
for(int i = 0; i < n - 1; i++){
mx = max(A[i] + k, right);
mn = min(A[i + 1] - k, left);
ret = min(ret, mx - mn);
}
return ret;
}
};
main(){
vector<int> v = {0, 10};
Solution ob;
cout << (ob.smallestRangeII(v, 2));
}輸入
[0,10] 2
輸出
6
更新於: 30-Apr-2020
196 瀏覽量
廣告