यहां हम देखेंगे कि कैसे जांचें कि एक असॉर्टेड सरणी में एक-दूसरे से k दूरी के भीतर डुप्लिकेट तत्व हैं या नहीं। मान लीजिए तत्वों की एक सूची है {1, 2, 3, 1, 4, 5}, यहां यदि k = 3 है, तो प्रोग्राम true लौटाएगा, क्योंकि दो 1s के बीच की दूरी 3 है।
हम इसे हैश टेबल का उपयोग करके हल करेंगे। चरण निम्नलिखित होंगे:
- एक खाली हैश टेबल बनाएं
- प्रत्येक इंडेक्स i के लिए, मान लें तत्व e = arr[i] सूची में है, तो
- यदि e हैश टेबल में मौजूद है, तो true लौटाएं
- अन्यथा, 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