在C ++中检查给定数组是否包含距每个k距离内的重复元素

在这里，我们将看到如何检查未排序的数组是否存在彼此之间k距离内的重复元素。假设元素列表为{1,2,3,1,4,5}，如果k = 3，则程序将返回true，因为两个1s之间的距离为3。

我们将使用哈希表解决此问题。步骤将如下所示-

• 创建一个空哈希表

• 对于每个索引i，令列表中的元素e = arr [i]，

• 如果哈希表中存在e，则返回true

• 否则，当i> = K时，将e添加到哈希表，并从哈希表中删除第(ik)个元素（如果存在）。

示例

#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