जांचें कि किसी दिए गए सरणी में सी ++ में प्रत्येक से k दूरी के भीतर डुप्लिकेट तत्व हैं या नहीं

यहां हम देखेंगे कि कैसे जांचा जाए कि एक अनसोल्ड ऐरे में एक दूसरे से k दूरी के भीतर डुप्लिकेट तत्व हैं या नहीं। मान लीजिए तत्वों की एक सूची {1, 2, 3, 1, 4, 5} है, यहां यदि k =3 है, तो प्रोग्राम सही होगा, क्योंकि दो 1s के बीच की दूरी 3 है।

हम इसे हैश टेबल का उपयोग करके हल करेंगे। चरण नीचे की तरह होंगे -

• एक खाली हैश तालिका बनाएं
• प्रत्येक अनुक्रमणिका i के लिए, सूची में तत्व e =arr[i] करने दें
  • यदि ई हैश तालिका में मौजूद है, तो सही लौटें
  • अन्यथा, हैश तालिका में e जोड़ें, और हैश तालिका से (i-k)वें तत्व को हटा दें, यदि यह मौजूद है, जब i>=K.

उदाहरण

#include<iostream>
#include<set>
using namespace std;
bool hasDuplicateWithDistK(int arr[], int n, int k) {
   set<int> element_set;
   for (int i = 0; i < n; i++) {
      if (element_set.find(arr[i]) != element_set.end())
         return true;
      element_set.insert(arr[i]);
      if (i >= k)
         element_set.erase(arr[i-k]);
   }
   return false;
}
int main () {
   int arr[] = {10, 5, 3, 4, 3, 5, 6};
   int n = sizeof(arr) / sizeof(arr[0]);
   if (hasDuplicateWithDistK(arr, n, 3))
      cout << "Duplicate element has found";
   else
      cout << "Duplicate element has not found";
}

आउटपुट

Duplicate element has found