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


난이도 쉽게
자주 묻는 질문 아마존 아 발라 라 FreeCharge HackerRank Snapchat 스냅 딜
배열 해시

"주어진 배열이 서로 k 거리 내에 중복 요소를 포함하는지 확인"문제는 k 범위 내에서 순서가 지정되지 않은 지정된 배열에서 중복 요소를 확인해야 함을 나타냅니다. 여기서 k의 값은 주어진 배열보다 작습니다.

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

K = 3   arr[] = {1, 2, 3, 4, 5, 2, 1}
False
K = 2   arr[] = {3, 4, 3, 1, 1, 2, 6}
True

설명

이 문제를 해결하는 방법에는 두 가지가 있습니다. 더 간단한 방법은 첫 번째 루프가 모든 요소를 ​​두 번째 루프 '내부 루프'의 시작 요소로 선택하는 두 개의 루프를 실행하는 것입니다. 그 후 두 번째 루프는 시작 요소를 'k'범위 내의 모든 요소와 비교합니다. 그러나이 솔루션은 O (k * n)의 시간 복잡성이 소요되는만큼 효율적이지 않습니다.

하지만 문제를 해결할 수있는 더 효율적인 방법이 있습니다. O (N) 시간 복잡도 해싱. 해싱 방법에서는 배열의 모든 요소를 ​​순회하고 요소가 존재하는지 여부를 확인합니다. 요소가 거기에 있으면 'True'를 반환합니다. 그렇지 않으면 'i'가 'k'보다 크거나 같으면 해시에 추가하고 해시에서 arr [ik] 요소를 제거합니다.

주어진 배열에 서로 k 거리 내에 중복 요소가 포함되어 있는지 확인하는 알고리즘

  1. 먼저 비어있는 해시 세트 여기에 배열의 요소를 저장할 것입니다.
  2. 배열의 모든 요소를 ​​왼쪽에서 오른쪽으로 순회합니다.
  3. 요소가 해시에 있는지 확인하십시오.
    • 거기에 있으면 "true"를 반환합니다.
    • 그렇지 않으면 해당 요소를 해시에 추가하십시오.
  4. 그 후 'I'가 'k'보다 크거나 같으면 해시에서 arr [ik] 요소를 제거합니다.

 

우리는 그 안에 몇 가지 요소가있는 배열 'arr []'와 중복을 찾아야하는 범위 인 k 값을 가지고 있습니다. 만약 존재한다면 그 안에 요소를 저장하기 위해 해시 세트를 사용할 것입니다. 해시 세트의 배열은 요소가 이미 해시 세트에 있으면 true를 반환하고 루프를 중단합니다. 그렇지 않으면 세트에 요소를 계속 삽입하고 세트에서 arr [ik] 요소를 제거합니다.

암호

주어진 배열에 서로 k 거리 내에 중복 요소가 포함되어 있는지 확인하는 C ++ 코드

#include<iostream>
#include<unordered_set>
using namespace std;

bool Check_Duplicates(int a[], int n, int k)
{

    unordered_set<int> D_set;

    for (int i = 0; i < n; i++)
    {
        if (D_set.find(a[i]) != D_set.end())
            return true;

        D_set.insert(a[i]);
        if (i >= k)
            D_set.erase(a[i-k]);
    }
    return false;
}

int main ()
{
    int a[] = {1, 2, 3, 4, 1};
    int k = 5;
    cout << ((Check_Duplicates(a, 5, k)) ? "Yes" : "No");
}
Yes

주어진 배열에 서로 k 거리 내에 중복 요소가 포함되어 있는지 확인하는 Java 코드

import java.util.*;
class D_Class
{
    static boolean Check_Duplicates(int a[], int k)
    {

        HashSet<Integer> D_set = new HashSet<>();

        for (int i=0; i<a.length; i++)
        {
            if (D_set.contains(a[i]))
                return true;

            D_set.add(a[i]);
            if (i >= k)
                D_set.remove(a[i-k]);
        }
        return false;
    }

    public static void main (String[] args)
    {
        int a[] = {1, 2, 3, 4, 1};
        int k = 5;

        if (Check_Duplicates(a, k))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
Yes

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 해시 세트를 사용하면 선형 시간으로 문제를 해결할 수 있습니다. 해시 세트를 사용하면 데이터를 효율적으로 검색, 삭제 및 삽입하는 기능이 향상됩니다.

공간 복잡성

확인) 어디에 "케이" 확인해야하는 창의 요소 수입니다.