주어진 배열에 C++의 각 요소로부터 k 거리 내에 중복 요소가 포함되어 있는지 확인하십시오.

여기에서는 정렬되지 않은 배열이 k 거리 내에 중복 요소가 있는지 여부를 확인하는 방법을 볼 것입니다. 요소 목록이 {1, 2, 3, 1, 4, 5}라고 가정하고 여기에서 k =3이면 두 1 사이의 거리가 3이므로 프로그램은 true를 반환합니다.

우리는 해시 테이블을 사용하여 이것을 해결할 것입니다. 단계는 아래와 같습니다 -

• 빈 해시 테이블 하나 만들기
• 각 인덱스 i에 대해 목록의 요소 e =arr[i]를 do
  • 해시 테이블에 e가 있으면 true를 반환합니다.
  • 그렇지 않으면 i>=K일 때 해시 테이블에 e를 추가하고 해시 테이블에서 (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