부분 배열의 고유 요소 수에 대한 쿼리


난이도 하드
자주 묻는 질문 아마존 구글 Microsoft 신탁 동네 짱
배열 세그먼트 트리 나무

우리는 정렬 정수와 질의의 수와 우리는 주어진 범위 내에서 우리가 가지고있는 모든 구별되는 요소의 수를 알아 내야합니다. 질의는 왼쪽과 오른쪽 두 숫자로 구성됩니다. 이것은 주어진 범위입니다. 고유 요소의 수를 찾으십시오.

입력:

arr [] = {2,3,4,1,1}

0, 4

1, 3

2, 4

출력:

+4 3 2 XNUMX

설명 :

첫 번째 쿼리에서 a [0… 4]의 고유 정수 개수는 4 (4, 3, 2,1)입니다. 두 번째 쿼리에서 a [1..3]의 고유 정수 수는 3 (4, 3,1)입니다. 세 번째 쿼리에서 a [2..4]의 고유 정수 수는 2 (1, 4)입니다.

주어진 범위 내에서 우리가 가진 모든 고유 요소의 수를 알아 내고,

암호알고리즘

  1. 객체 배열을 만들고 각 위치로 값을 왼쪽, 오른쪽 및 각 값과 관련된 인덱스로 표시하십시오. 대상.
  2. 범위로 제공된 올바른 값을 기준으로 쿼리 배열을 정렬합니다.
  3. binaryIndTree [] 배열을 만듭니다.
  4. 주어진 배열과 동시에 주어진 쿼리를 탐색하기 시작합니다.
  5. visitArray [a [i]]가 -1인지 확인하십시오.
  6. false이면, visitArray [a [i]] 인덱스에서 -1 값으로 binaryIndTree 배열을 업데이트합니다.
  7. visitArray [a [i]] = i를 설정하고 인덱스 i에서 값 1로 binaryIndTree 배열 binaryIndTree 배열을 업데이트합니다.
  8. 카운터를 0으로 설정하고 카운터가 쿼리 개수보다 적을 때까지 그리고 쿼리 오른쪽 값이 i와 같을 때까지 트래버스를 시작합니다.
  9. 객체의 각 쿼리 인덱스에 대해 배열은 쿼리의 오른쪽 값과 쿼리의 왼쪽 값의 차이로 값 쿼리 인덱스를 업데이트합니다.
  10. 정의 된 각 쿼리에 대한 모든 결과를 인쇄합니다.

설명

우리는 그 객체 배열로 우리가 왼쪽, 오른쪽 및 인덱스 또는 쿼리 수를 연결하도록 객체 배열을 만들 것입니다. 그런 다음 쿼리 배열이 'right'값의 오름차순으로 정렬되도록 해당 쿼리 개체를 정렬 할 것입니다. 즉, 'right'값이 가장 작은 쿼리가 순서대로 먼저 오게됩니다.

이제 binaryIndTree 인 배열을 만듭니다. 배열의 모든 값을 0으로 초기화 한 다음 최대 크기의 배열 (1000001)을 만듭니다.이 배열의 모든 값을 -1로 초기화하고 크기 쿼리 출력의 마지막 배열을 초기화합니다. 쿼리 수로 출력합니다. 카운터의 값은 0으로 설정되어야합니다. 이제 배열을 탐색하기 시작하고 visitArray [arr [i]] = -1인지 확인하고 true이면 binaryIndTree 값을 -1 값으로 업데이트합니다. 업데이트 후 visitArray [arr [i]] 값을 i로 업데이트하고 다시 binaryIndTree를 값 1로 업데이트하면 위 조건이 참인지 아닌지에 관계없이 수행됩니다.

이 루프 내에서 배열 업데이트를 시작하면 카운터 값이 쿼리 번호 q의 값보다 작을 때까지 수행됩니다. 쿼리의 오른쪽 값과 쿼리의 왼쪽 값의 차이로 출력 배열을 업데이트하고 각 인덱스에서 업데이트합니다. 쿼리 수와 동일한 인덱스를 생성 할 때를 기억하십시오. 그리고 카운터 값을 높이십시오. 마지막으로 출력 배열의 모든 값을 인쇄합니다.

실시

하위 배열의 고유 요소 수 쿼리를위한 C ++ 프로그램

#include<bits/stdc++.h>

using namespace std;

const int MAX = 1000001;

struct Query
{
    int left, right, index;
};

bool compare(Query x, Query y)
{
    return x.right < y.right;
}

void update(int index, int val, int binaryIndTree[], int n)
{
    for (; index <= n; index += index&-index)
        binaryIndTree[index] += val;
}

int query(int index, int binaryIndTree[], int n)
{
    int sum = 0;
    for (; index>0; index-=index&-index)
        sum += binaryIndTree[index];
    return sum;
}

void getQueryOutput(int arr[], int n, Query queries[], int q)
{
    int binaryIndTree[n+1];
    memset(binaryIndTree, 0, sizeof(binaryIndTree));

    int visitedArray[MAX];
    memset(visitedArray, -1, sizeof(visitedArray));

    int output[q];
    int counter = 0;
    for (int i=0; i<n; i++)
    {
        if (visitedArray[arr[i]] !=-1)
            update (visitedArray[arr[i]] + 1, -1, binaryIndTree, n);

        visitedArray[arr[i]] = i;
        update(i + 1, 1, binaryIndTree, n);

        while (counter < q && queries[counter].right == i)
        {
            output[queries[counter].index] = query(queries[counter].right + 1, binaryIndTree, n)- query(queries[counter]. left, binaryIndTree, n);
            counter++;
        }
    }
    for (int i=0; i<q; i++)
        cout << output[i] << endl;
}

int main()
{
    int a[] = { 2,3,4,1,1};
    int n = sizeof(a)/sizeof(a[0]);
    Query queries[3];
    queries[0].left = 0;
    queries[0].right = 4;
    queries[0].index = 0;
    queries[1].left = 1;
    queries[1].right = 3;
    queries[1].index = 1;
    queries[2].left = 2;
    queries[2].right = 4;
    queries[2].index = 2;
    int q = sizeof(queries)/sizeof(queries[0]);
    sort(queries, queries+q, compare);
    getQueryOutput(a, n, queries, q);
    return 0;
}
4
3
2

하위 배열의 고유 요소 수에 대한 쿼리를위한 Java 프로그램

import java.util.Arrays;
import java.util.Comparator;

class distinctElementsQuery
{
    static int MAX = 1000001;

    static class Query
    {
        int l, r, index;
    }

    static void update(int index, int val, int binaryIndTree[], int n)
    {
        for (; index <= n; index += index & -index)
            binaryIndTree[index] += val;
    }
    static int query(int index, int binaryIndTree[], int n)
    {
        int sum = 0;
        for (; index > 0; index -= index & -index)
            sum += binaryIndTree[index];
        return sum;
    }
    static void getQueryOutput(int[] arr, int n, Query[] queries, int q)
    {
        int[] binaryIndTree = new int[n + 1];
        Arrays.fill(binaryIndTree, 0);

        int[] visitedArray = new int[MAX];
        Arrays.fill(visitedArray, -1);

        int[] output = new int[q];
        int counter = 0;
        for (int i = 0; i < n; i++)
        {
            if (visitedArray[arr[i]] != -1)
                update(visitedArray[arr[i]] + 1, -1, binaryIndTree, n);

            visitedArray[arr[i]] = i;
            update(i + 1, 1, binaryIndTree, n);

            while (counter < q && queries[counter].r == i)
            {
                output[queries[counter].index] = query(queries[counter].r + 1, binaryIndTree, n) - query(queries[counter].l, binaryIndTree, n);
                counter++;
            }
        }
        for (int i = 0; i < q; i++)
            System.out.println(output[i]);
    }
    public static void main(String[] args)
    {
        int a[] = { 2,3,4,1,1};
        int n = a.length;
        Query[] queries = new Query[3];
        for (int i = 0; i < 3; i++)
            queries[i] = new Query();
        queries[0].l = 0;
        queries[0].r = 4;
        queries[0].index = 0;
        queries[1].l = 1;
        queries[1].r = 3;
        queries[1].index = 1;
        queries[2].l = 2;
        queries[2].r = 4;
        queries[2].index = 2;
        int q = queries.length;
        Arrays.sort(queries, new Comparator<Query>()
        {
            public int compare(Query x, Query y)
            {
                if (x.r < y.r)
                    return -1;
                else if (x.r == y.r)
                    return 0;
                else
                    return 1;
            }
        });
        getQueryOutput(a, n, queries, q);
    }
}
4
3
2

하위 배열의 고유 요소 수에 대한 쿼리에 대한 복잡성 분석

시간 복잡성

O (쿼리 * log n) 어디에 "엔" 입력 배열의 크기입니다.

공간 복잡성

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

참고