এখানে আমরা দেখব কিভাবে একটি আনসোর্টেড অ্যারেতে k দূরত্বের মধ্যে ডুপ্লিকেট উপাদান আছে কিনা তা যাচাই করা যায়। ধরুন একটি তালিকা আছে {1, 2, 3, 1, 4, 5}, এখানে যদি k = 3 হয়, তবে প্রোগ্রামটি true রিটার্ন করবে, কারণ দুটি ১-এর মধ্যে দূরত্ব ৩।
এই সমস্যাটি হ্যাশ টেবিল ব্যবহার করে সমাধান করা যায়। ধাপগুলো নিচে দেওয়া হলো:
- একটি খালি হ্যাশ টেবিল তৈরি করুন।
- প্রতিটি ইন্ডেক্স 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
