C++ में डुप्लीकेट III शामिल है

मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी है, हमें यह जांचना होगा कि क्या सरणी में दो अलग-अलग सूचकांक 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