ที่นี่เราจะดูวิธีการตรวจสอบว่าอาร์เรย์ที่ไม่เรียงลำดับมีองค์ประกอบที่ซ้ำกันภายในระยะ k จากกันหรือไม่ สมมติว่ารายการองค์ประกอบคือ {1, 2, 3, 1, 4, 5} ในที่นี้หาก k =3 โปรแกรมจะคืนค่าเป็นจริง เนื่องจากระยะห่างระหว่าง 1 วินาทีคือ 3
เราจะแก้ปัญหานี้โดยใช้ตารางแฮช ขั้นตอนจะเป็นดังนี้ -
- สร้างตารางแฮชเปล่าหนึ่งตาราง
- สำหรับแต่ละดัชนี i ให้องค์ประกอบ e =arr[i] ในรายการ ทำ
- ถ้ามี e ในตารางแฮช ให้คืนค่า true
- มิฉะนั้น ให้เพิ่ม e ลงในตารางแฮช และลบองค์ประกอบ (i-k)th ออกจากตารางแฮช หากมี เมื่อ 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
