サブアレイ内の個別の要素の数に関するクエリ


難易度 ハード
よく聞かれる Amazon (アマゾン) Google マイクロソフト オラクル ユーバー
配列 セグメントツリー

私たちは与えました 配列 整数とクエリの数であり、指定された範囲内にあるすべての個別の要素の数を見つける必要があります。クエリは左右のXNUMXつの数値で構成されます。これは指定された範囲であり、この指定された範囲は個別の要素の数を調べます。

入力:

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

0、4

1、3

2、4

出力:

4 3 2

説明:

最初のクエリでは、a [0…4]内の個別の整数の数は4(4、3、2,1、1)です。 3番目のクエリでは、a [3..4]内の個別の整数の数は3,1(2、4)です。 2番目のクエリでは、a [1..4]内の個別の整数の数はXNUMX(XNUMX、XNUMX)です。

与えられた範囲内にあるすべての異なる要素の数を見つけます。

アルゴリズム

  1. オブジェクト配列を作成し、各位置で値を左、右、およびそれぞれに関連付けられたインデックスとしてマークします オブジェクト.
  2. 範囲として指定された正しい値に関してクエリ配列を並べ替えます。
  3. 配列binaryIndTree []を作成します。
  4. 指定された配列と同時に指定されたクエリのトラバースを開始し、
  5. visitedArray [a [i]]が-1であるかどうかを確認します。
  6. falseの場合、visitedArray [a [i]]のインデックスでbinaryIndTree配列を値-1で更新します。
  7. visitedArray [a [i]] = iを設定し、binaryIndTree配列binaryIndTree配列をインデックスiの値1で更新します。
  8. カウンターを0に設定し、カウンターがクエリの数より少なくなるまで、またクエリの正しい値がiに等しくなるまでトラバースを開始します。
  9. オブジェクトのクエリのインデックスごとに、配列はクエリの右の値とクエリの左の値の差として値クエリインデックスを更新します。
  10. 定義された各クエリのすべての結果を出力します。

説明

オブジェクト配列を作成して、そのオブジェクト配列を使用して、左、右、およびクエリのインデックスまたは番号をリンクします。 次に、クエリ配列が「right」値の昇順で並べ替えられるように、そのクエリオブジェクトを並べ替えます。これは、「right」の値が最も小さいクエリが最初に来ることを意味します。

次に、binaryIndTreeである配列を作成します。 配列のすべての値を0で初期化し、次にサイズmaxの配列(1000001)を作成します。この配列のすべての値を-1に初期化し、サイズクエリの出力の最後の配列を初期化します。クエリ数として出力します。 カウンターの値を0に設定する必要があります。次に、配列のトラバースを開始し、visitedArray [arr [i]] = -1であるかどうかを確認し、trueであることが判明した場合は、binaryIndTreeの値を値-1で更新します。 値visitedArray [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(クエリ*ログn) where 「n」 入力配列のサイズです。

スペースの複雑さ

O(N) where 「n」 配列の要素数です。

参照