Computer >> Máy Tính >  >> Lập trình >> C ++

Phạm vi nhỏ nhất II trong C ++

Giả sử chúng ta có một mảng A gồm các số nguyên, với mỗi số nguyên A [i], chúng ta phải chọn x =-K hoặc x =K, và thêm x vào A [i] (chỉ một lần). Vì vậy, sau quá trình này, chúng ta có một số mảng B. Chúng ta phải tìm sự khác biệt nhỏ nhất có thể giữa giá trị lớn nhất của B và giá trị nhỏ nhất của B. Vì vậy, nếu đầu vào là A =[0,10], K =2, thì đầu ra sẽ là 6, vì B =[2,8].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • đặt ret:=0, n:=kích thước của mảng A

  • sắp xếp mảng A

  • set ret:=Phần tử cuối cùng của A - phần tử đầu tiên của A

  • right:=Phần tử cuối cùng của A - K và bên trái:=phần tử đầu tiên của A + k

  • cho tôi trong phạm vi từ 0 đến n - 1

    • mx:=max of A [i] + k và right

    • mn:=min of A [i + 1] - k and left

    • ret:=min trong tổng số ret và (mx - min)

  • trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

#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));
}

Đầu vào 

[0,10]
2

Đầu ra 

6