k 개의 고유 한 수를 갖는 최소 부분 배열

난이도 하드
자주 묻는 질문 아마존 구글
배열 해시 슬라이딩 윈도우 두 포인터조회수 38

정수가 있다고 가정합니다. 정렬 그리고 숫자 k. 문제 설명은 범위 (l, r)의 가장 작은 하위 배열을 포함하여 가장 작은 하위 배열에 정확히 k 개의 고유 한 숫자가있는 방식을 찾아야합니다.

입력:

{1, 2, 2, 3, 4, 5, 5}

k = 3

출력:

2, 4

설명 :

{2, 3, 4}는 2에서 시작하는 가장 작은 하위 배열입니다.nd 4로 색인th k 즉, 3 개의 개별 요소가있는 인덱스.

입력:

{2, 5, 6, 7}

k = 2

출력:

2, 3

설명 :

{2, 5}는 ​​두 번째 인덱스부터 세 번째 인덱스까지 k 즉, 2 개의 개별 요소가있는 가장 작은 하위 배열입니다.

암호알고리즘

  1. 고유 요소를 0으로 설정하고 왼쪽 및 오른쪽 포인터를 -1로 설정합니다.
  2. 배열을 통해 이동합니다.
  3. 주어진 수 k보다 작은 고유 요소가 없으면 오른쪽을 1 씩 증가시킵니다.
  4. 그런 다음 개수를 늘리고 배열 요소의 빈도를 지도.
  5. 고유 요소가 주어진 숫자 k와 같고 이렇게 형성된 길이가 이전에 업데이트 된 길이보다 작 으면 왼쪽 및 오른쪽 포인터가 중단됩니다.
  6. 고유 요소의 수가 k 미만인 것으로 확인되면 중단됩니다.
  7. 고유 요소의 수가 k와 같은지 확인한 다음 오른쪽 포인터를 늘립니다.
  8. 고유 요소가 주어진 숫자 k와 같고 이렇게 형성된 길이가 이전에 업데이트 된 길이보다 작 으면 왼쪽 및 오른쪽 포인터가 중단됩니다.
  9. 요소의 빈도가 1인지 확인한 다음지도에서 해당 요소를 제거하고, 그렇지 않으면 해당 요소의 빈도 수를 줄입니다.
  10. 왼쪽 포인터가 0이고 오른쪽이 n이면 해당 포인터가 유효하지 않음을 의미합니다.
  11. 그렇지 않으면 왼쪽 및 오른쪽 값을 인쇄하십시오.

설명

배열을 순회하는 동안 각 배열 요소 빈도를 저장하고 각 배열 요소를 선택하고 해당 배열 요소의 빈도를 계산하고 저장하는 데 필요한 것보다 k 미만인 경우 맵 크기가 k 미만인지 확인하고 맵 크기가 k (고유 요소 번호)이고 현재 길이가 하위 배열의 이전 길이보다 작다는 것을 확인한 다음 왼쪽 및 오른쪽 포인터를 업데이트합니다. 이 모든 것은 전체지도가 한 번 통과 할 때까지 반복됩니다.

지도의 크기가 k보다 작 으면 중단됩니다. 지도에 값이 있습니다. 루프는 맵의 크기가 k와 같고 맵의 배열 요소의 빈도가 1이 될 때까지 이동합니다. 그런 다음 맵에서 특정 요소를 제거해야합니다. 그렇지 않으면 지도에서 특정 요소의 빈도. 다시지도 크기가 k와 같고 현재 하위 배열의 길이가 이전에 업데이트 된 길이보다 작은 지 확인한 다음 왼쪽 및 오른쪽 포인터를 업데이트합니다. 배열 요소의 빈도가 1이면 해당 요소를 제거하고 요소의 빈도를 줄입니다.

배열을 순회 한 후 왼쪽 포인터가 0이고 오른쪽 포인터가 n 인 경우 잘못된 k임을 의미합니다. 그렇지 않으면 가장 작은 하위 배열의 시작 지점과 끝 지점이 될 왼쪽 및 오른쪽 포인터의 값을 인쇄합니다.

실시

k 개의 고유 한 숫자를 가진 가장 작은 부분 배열을위한 C ++ 프로그램

#include<map>

using namespace std;

void getSmallestSubarray(int arr[], int n, int k)
{
    int left = 0, right = n;
    int j = -1;
    map<int, int> MAP;
    for (int i=0; i<n; i++)
    {
        while (j < n)
        {
            j++;
            if (MAP.size() < k)
                MAP[arr[j]]++;

            if (MAP.size() == k && ((right - left) >= (j - i)))
            {
                left = i;
                right = j;
                break;
            }

        }
        if (MAP.size() < k)
            break;

        while (MAP.size() == k)
        {
            if (MAP[arr[i]] == 1)
                MAP.erase(arr[i]);
            else
                MAP[arr[i]]--;

            i++;

            if (MAP.size() == k && (right - left) >= (j - i))
            {
                left = i;
                right = j;
            }
        }
        if (MAP[arr[i]] == 1)
            MAP.erase(arr[i]);
        else
            MAP[arr[i]]--;
    }
    if (left == 0 && right == n)
        cout << "Invalid k" << endl;
    else
        cout << left << " " << right;
}
int main()
{
    int arr[] = {1, 2, 2, 3, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getSmallestSubarray(arr, n, k);
    return 0;
}
2 4

k 개의 고유 한 숫자를 가진 가장 작은 부분 배열을위한 Java 프로그램

import java.util.HashMap;
import java.util.Map;
class smallestSubArray
{
    public static void getSmallestSubarray(int arr[], int n, int k)
    {
        int left = 0, right = n;
        int j = -1;
        HashMap<Integer, Integer> MAP=new HashMap<>();
        for (int i=0; i<n; i++)
        {
            while (j < n-1)
            {
                j++;
                if (MAP.size() < k)
                {

                    if(MAP.containsKey( arr[j] ))
                        MAP.put( arr[j], MAP.get( arr[j] ) + 1 );
                    else
                        MAP.put(arr[j],1);
                }

                if (MAP.size() == k && ((right - left) >= (j - i)))
                {
                    left = i;
                    right = j;
                    break;
                }
            }
            if (MAP.size() < k)
                break;

            while (MAP.size() == k)
            {
                if (MAP.get(arr[i]) == 1)
                    MAP.remove(arr[i]);
                else
                    MAP.put(arr[i], MAP.get(arr[i])-1);

                i++;

                if (MAP.size() == k && (right - left) >= (j - i))
                {
                    left = i;
                    right = j;
                }
            }
            if (MAP.get(arr[i]) == 1)
                MAP.remove(arr[i]);
            else
                MAP.put(arr[i], MAP.get(arr[i])-1);
        }
        if (left == 0 && right == n)
            System.out.println("Invalid k");
        else
            System.out.println(left+" "+right);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, 2, 2, 3, 4, 5, 5};
        int n = arr.length;
        int k = 3;
        getSmallestSubarray(arr, n, k);

    }
}
2 4

k 개의 고유 한 수를 갖는 가장 작은 부분 배열에 대한 복잡도 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

Translate »