크기 K의 모든 창에서 고유 요소 계산


난이도 중급
자주 묻는 질문 Accolite 아마존 Microsoft
배열 해시 슬라이딩 윈도우

서브 세트는 우리가 지금 당분간 다루어 온 것입니다. 지난 에피소드에서 우리는 뚜렷한 짝수로 만들 수있는 부분 집합의 수를 다루었습니다. 이번에는 K 크기의 모든 창에서 고유 한 요소를 계산합니다.

섹션 1

문제에 대해.

정렬되지 않은 정수 배열이 주어집니다. 우리는 각 부분 집합이 갖는 정수의 고유 한 수를 알아 내야합니다. 샘플 테스트 케이스로 설명을 확인하겠습니다.

주어진:

배열 : {1,2,3,4,4,2,3}

하위 집합의 크기 : 4

가능한 하위 집합은 다음과 같습니다.

1,2,3,4 {{}}

2,3,4,4 {{}}

3,4,4,2 {{}}

4,4,2,3 {{}}

위의 각 하위 집합에서 고유 한 번호는 다음과 같습니다.

4,3,2 및 3

섹션 2

문제에 접근 할 수있는 방법은 여러 가지가 있습니다. 그러나 나는 나머지 중에서 가장 좋은 것을 논의 할 것입니다. 하위 집합을 확장함에 따라 내 청중은 패턴을 발견했을 것입니다. 각 창에 대해 k의 크기를 유지하기 위해 새 요소를 추가 할 때 마지막 창에서 첫 번째 요소를 놓았습니다.

과정을 하나씩 살펴 보자

  • 먼저 k의 루프를 실행하여 첫 번째 창의 모든 요소를 ​​반복합니다.
  • HashMap으로 모든 요소 수 유지
  • 키는 HashMap에서 요소가 발생한 횟수 인 값을 가진 요소입니다.
  • 앞으로 나아가면서 HashMap에서 첫 번째 요소를 제거합니다.
  • 요소가 한 번만 발생하면 간단히 제거합니다.
  • 그렇지 않으면 HashMap에서 요소의 발생 횟수를 줄입니다.
  • 우리는 신선한 요소를 확인합니다.
  • 사전에 존재하는 경우. 우리는 그 발생에 추가합니다.
  • 존재하지 않는 경우 HashMap에 추가합니다.
  • 각 반복에서 고유 요소의 개수를 ArrayList에 추가하거나 출력 할 수 있습니다.
  • 고유 요소의 개수는 HashMap의 크기입니다.

다음은 프로세스 개요를 제공하는 이미지입니다.

여기에 크기 6의 배열이 있고 k는 3으로 주어졌습니다. 빨간색 강조 표시는 슬라이딩 창을 이동할 때 하위 집합입니다.

크기 K의 모든 창에서 고유 요소 계산
창 크기 3에 대한 하위 집합 표시

크기 K의 모든 창에서 고유 요소 개수를 계산하는 Java 코드

// "static void main" must be defined in a public class.
public class Main 
{
    public static void countDist(int[] arr,int k)
    {
        HashMap<Integer,Integer>store=new HashMap<Integer,Integer>();
        List<Integer>ans=new ArrayList<Integer>();
        for(int i=0;i<k;i++)
        {
            if(!store.containsKey(arr[i]))
                store.put(arr[i],1);
            else
                store.put(arr[i],store.get(arr[i])+1);
        }
        ans.add(store.size());
        for(int i=k;i<arr.length;i++)
        {
            if(store.get(arr[i-k])==1)
                store.remove(arr[i-k]);
            else
                store.put(arr[i-k],store.get(arr[i-k])-1);
            if(!store.containsKey(arr[i]))
                store.put(arr[i],1);
            else
                store.put(arr[i],store.get(arr[i])+1);
            ans.add(store.size());
        }
        for(int i=0;i<ans.size();i++)
            System.out.print(ans.get(i)+" ");
    }
    public static void main(String[] args) 
    {
        int arr[] = { 1, 2, 1, 3, 4, 2, 3 }; 
        int k = 4; 
        countDist(arr, k); 
    }
}

Java에서 C ++로 전환합니다. 우리는 컬렉션 프레임 워크 STL에. 즉, HashMap 대신 정렬되지 않은 맵을 사용하고 ArrayList 대신 벡터를 사용합니다.

이제 C ++ 용 코드로 전환 해 보겠습니다.

크기 K의 모든 창에서 고유 요소 개수를 계산하는 C ++ 코드

#include<bits/stdc++.h>
using namespace std;
void countDist(int arr[],int k,int size)
{
        unordered_map<int,int>store;
        vector<int>ans;
        for(int i=0;i<k;i++)
        {
            if(store.find(arr[i])==store.end())
                store[arr[i]]=1;
            else
                store[arr[i]]=store[arr[i]]+1;
        }
        ans.push_back(store.size());
        for(int i=k;i<size;i++)
        {
            if(store[arr[i-k]]==1)
                store.erase(arr[i-k]);
            else
                store[arr[i-k]]=store[arr[i-k]]-1;
            if(store.find(arr[i])!=store.end())
                store[arr[i]]=1;
            else
                store[arr[i]]=store[arr[i]]+1;
            ans.push_back(store.size());
        }
        for(int i=0;i<ans.size();i++)
            cout<<ans[i]<<" ";
}
int main() 
{ 
    int arr[] = { 1, 2, 1, 3, 4, 2, 3 }; 
    int size = sizeof(arr) / sizeof(arr[0]); 
    int k = 4; 
    countDist(arr, k, size); 
  
    return 0; 
}
3 4 4 3

크기 K의 모든 창에서 고유 요소 개수에 대한 복잡성 분석

시간 복잡성 = O (n)

공간 복잡성 = O (k)

어떻게?

시간 복잡성 정보

  • 요소를 검색 할 때
  • 첫 번째 루프는 k 요소에 대해 실행됩니다.
  • 그런 다음 실행하는 루프는 첫 번째 요소를 선택한 다음 마지막 요소를 고려합니다.
  • 이런 식으로 적어도 한 번은 모든 요소를 ​​선택했습니다.
  • 이것은 시간 복잡성을 O (n)으로 만듭니다.

공간 복잡성 정보

  • 우리가 가지고있는 HashMap은 한 번에 k 개의 요소 만 취합니다.
  • HashMap은 첫 번째 루프에서 처음 k 요소를 사용합니다.
  • 앞으로 나아가면서 오래된 요소를 제거하고 새로운 요소를 추가합니다.
  • 반복되는 경우 요소가 적을 수 있습니다.
  • 요소가 모두 구별되는 경우 k 요소가 있습니다.

참조