Kiểm tra mảng có phần tử trùng lặp trong khoảng cách k trong C++

Chúng ta sẽ xem cách kiểm tra một mảng không sắp xếp có chứa các phần tử trùng lặp ở khoảng cách không quá k hay không. Ví dụ mảng {1, 2, 3, 1, 4, 5}, với k = 3 thì kết quả là true vì khoảng cách giữa hai số 1 là 3.

Giải pháp dùng bảng băm (hash table):

• Tạo một bảng băm rỗng.
• Duyệt qua từng chỉ số i, phần tử e = arr[i]:
  • Nếu e đã có trong bảng băm, trả về true.
  • Ngược lại, thêm e vào bảng băm, và xóa phần tử ở vị trí i-k nếu i >= k.

Ví dụ

#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";
}

Kết quả

Duplicate element has found