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排序
setret:=A的最后一个元素–A的第一个元素
右:=A–K的最后一个元素,左:=A+k的第一个元素
对于i,范围为0至n–1
mx:=A[i]+k的最大值,右
mn:=A[i+1]–k的最小值,然后左
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