मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी है, हमें यह जांचना होगा कि क्या सरणी में दो अलग-अलग सूचकांक i और j हैं जैसे कि nums[i] और nums[j] के बीच पूर्ण अंतर अधिकतम टी. और i और j के बीच पूर्ण अंतर अधिकतम k है। इसलिए यदि इनपुट [1,2,3,1] जैसा है, तो यदि k =3 और t =0 है, तो सही लौटें।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक सेट बनाएं s, n :=nums array का आकार
-
मैं के लिए 0 से n - 1 की सीमा में
-
x अंक [i] और ऊपर से शुरू होने वाले सेट तत्व की अनुक्रमणिका है
-
यदि x सेट की सीमा में नहीं है और x <=nums[i] + t का मान है, तो सही लौटें
-
अगर x पहला तत्व नहीं है
-
x :=अगला तत्व यादृच्छिक के रूप में
-
यदि x से शुरू होने वाला t वां तत्व>=nums[i] है, तो सही लौटें
-
-
nums[i] को s में डालें, फिर nums[i - k] को s से हटाएँ
-
-
झूठी वापसी
उदाहरण(C++)
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
multiset <int> s;
int n = nums.size();
for(int i = 0; i< n; i++){
multiset <int> :: iterator x = s.lower_bound(nums[i]);
if(x != s.end() && *x <= nums[i] + t ) return true;
if(x != s.begin()){
x = std::next(x, -1);
if(*x + t >= nums[i])return true;
}
s.insert(nums[i]);
if(i >= k){
s.erase(nums[i - k]);
}
}
return false;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,1};
cout << (ob.containsNearbyAlmostDuplicate(v, 3,0));
} इनपुट
[1,2,3,1] 3 0
आउटपुट
1
