ตรวจสอบว่า Array มี Duplicate Elements อยู่ในระยะ k หรือไม่ใน C++

ในบทความนี้เราจะมาดูวิธีการตรวจสอบว่า Unsorted Array มี Duplicate Elements ที่อยู่ห่างกันไม่เกิน k หรือไม่ ตัวอย่างเช่น Array {1, 2, 3, 1, 4, 5} ถ้า k = 3 โปรแกรมจะคืนค่า true เพราะระยะห่างระหว่างเลข 1 ทั้งสองตัวคือ 3

เราจะแก้ปัญหานี้โดยใช้ Hash Table ขั้นตอนมีดังนี้:

• สร้าง Hash Table ว่าง
• สำหรับแต่ละ index i ให้ element e = arr[i] ทำดังนี้:
  • ถ้า e อยู่ใน Hash Table แล้ว ให้คืนค่า true
  • มิฉะนั้น ให้เพิ่ม e ลงใน Hash Table และลบ element ที่ index (i-k) ออกจาก Hash Table ถ้ามีอยู่ เมื่อ i >= k

ตัวอย่างโค้ด C++

#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