मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी A है, प्रत्येक पूर्णांक A[i] के लिए हमें या तो x =-K या x =K चुनना है, और x को A[i] में जोड़ना है (केवल एक बार)। तो इस प्रक्रिया के बाद, हमारे पास कुछ सरणी बी है। हमें बी के अधिकतम मूल्य और बी के न्यूनतम मूल्य के बीच सबसे छोटा संभव अंतर खोजना होगा। इसलिए यदि इनपुट ए =[0,10], के =2 है, तो आउटपुट 6 होगा, जैसा कि बी =[2,8]।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
रिट सेट करें:=0, एन:=सरणी ए का आकार
-
सरणी A को सॉर्ट करें
-
सेट रिट:=ए का अंतिम तत्व - ए का पहला तत्व
-
दायां:=A – K का अंतिम तत्व और बायां:=A + k का पहला तत्व
-
मेरे लिए 0 से n - 1 की सीमा में
-
mx :=अधिकतम A[i] + k और दाएँ
-
mn :=मिनट A[i + 1] – k और बाएँ
-
रिट :=मिनट का रिट और (एमएक्स - मिनट)
-
-
वापसी रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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