Ở đây chúng ta sẽ xem cách kiểm tra xem một mảng không được sắp xếp có các phần tử trùng lặp trong khoảng cách k cách xa nhau hay không. Giả sử danh sách các phần tử là {1, 2, 3, 1, 4, 5}, ở đây nếu k =3 thì chương trình sẽ trả về true, vì khoảng cách giữa hai phần tử 1 là 3.
Chúng tôi sẽ giải quyết điều này bằng cách sử dụng một bảng băm. Các bước sẽ như dưới đây -
- Tạo một bảng băm trống
- Đối với mỗi chỉ mục i, hãy để phần tử e =arr [i] trong danh sách, thực hiện
- nếu e có trong bảng băm, thì trả về true
- nếu không, hãy thêm e vào bảng băm và xóa phần tử thứ (i-k) khỏi bảng băm nếu nó tồn tại, khi 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";
} Đầu ra
Duplicate element has found