特定の配列に、C++でそれぞれからk距離以内に重複する要素が含まれているかどうかを確認します

ここでは、ソートされていない配列に、互いにk距離以内に重複する要素があるかどうかを確認する方法を説明します。要素のリストが{1、2、3、1、4、5}であると仮定します。ここで、k =3の場合、2つの1の間の距離は3であるため、プログラムはtrueを返します。

ハッシュテーブルを使用してこれを解決します。手順は次のようになります-

• 空のハッシュテーブルを1つ作成します
• 各インデックスiについて、リスト内の要素e =arr[i]とします。
  • ハッシュテーブルにeが存在する場合は、trueを返します
  • それ以外の場合は、ハッシュテーブルにeを追加し、i> =Kの場合、ハッシュテーブルから（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