ধরুন আমাদের পূর্ণসংখ্যার একটি অ্যারে রয়েছে, প্রতিটি পূর্ণসংখ্যা A[i] এর জন্য আমাদেরকে x =-K বা x =K বেছে নিতে হবে এবং A[i] এর সাথে x যোগ করতে হবে (শুধু একবার)। সুতরাং এই প্রক্রিয়ার পরে, আমাদের কিছু অ্যারে B আছে। আমাদের B-এর সর্বোচ্চ মান এবং B-এর সর্বনিম্ন মানের মধ্যে সম্ভাব্য ক্ষুদ্রতম পার্থক্য খুঁজে বের করতে হবে। তাই যদি ইনপুটটি A =[0,10], K =2 হয়, তাহলে আউটপুট হবে 6, যেমন B =[2,8]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
সেট ret :=0, n :=অ্যারের আকার A
-
অ্যারে সাজান A
-
সেট ret :=A এর শেষ উপাদান - A এর প্রথম উপাদান
-
ডানে :=A – K এর শেষ উপাদান এবং বাম :=A + k
এর প্রথম উপাদান -
0 থেকে n – 1
রেঞ্জের i জন্য-
mx :=A[i] + k এবং ডানের সর্বাধিক
-
mn :=A[i + 1] - k এবং বাম
এর মিনিট -
ret :=ret এর মিনিট এবং (mx - মিনিট)
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
