Ішкі тордағы ерекше элементтердің саны туралы сұраулар


Күрделілік дәрежесі қиын
Жиі кіреді Amazon Google Microsoft Oracle қиятын
Array Сегмент ағашы ағаш

Біз ан массив бүтін және бірнеше сұраулардан тұрады және біз берілген ауқымдағы барлық нақты элементтердің санын білуіміз керек, сұрау солға және оңға екі сандардан тұрады, бұл берілген диапазон, берілген шектерде нақты элементтердің санын анықтау.

мысал

Кіру:

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

0, 4

1, 3

2, 4

Шығару:

4 3 2

Түсіндіру:

Бірінші сұрауда 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. Егер жалған болса, binaryIndTree жиымын -1 мәні бар VisitArray индексінде жаңартыңыз [a [i]].
  7. VisitArray [a [i]] = i орнатыңыз және binaryIndTree жиымын binaryIndTree жиымын 1 индексінде XNUMX мәнімен жаңартыңыз.
  8. Есептегішті 0-ге қойып, санауыш сұраныс жоқ болғанға дейін және сұраныстың оң мәні i-ге тең болғанша траверсті бастаңыз.
  9. Нысанның әрбір сұраныстар индексі үшін массив сұраныстар индексін сұраулардың оң мәні мен сұраныстардың сол мәнінің айырмасы ретінде жаңартады.
  10. Анықталған әрбір сұраныс бойынша барлық нәтижелерді басып шығарыңыз.

Түсіндіру

Біз объект массивін сол объекті массивімен солға, оңға және индексті немесе сұраныс санын байланыстыратындай етіп жасаймыз. Содан кейін біз сұрау объектісін сұрыптау массивін 'дұрыс' мәндерінің өсу ретімен сұрыптайтындай етіп сұраймыз, 'оң' ең аз мәні бар сұраныс бірінші кезекте болатынын білдіреді.

Енді binaryIndTree жиымын жасаңыз. Массивтің барлық мәндерін 0 мәнімен инициализациялаңыз, содан кейін 1000001 болатын максимум массивін құрыңыз. Бұл жиымның барлық мәндерін -1-ге дейін және өлшем сұранысы шығарылымының соңғы жиымына инициализациялаңыз, өйткені онда бірдей саны болады сұраныстар саны ретінде шығарылады. Есептегіштің мәні 0-ге теңестірілуі керек. Енді біз массивті аралай бастаймыз және visitArray [arr [i]] = -1 екенін тексереміз, егер ол дұрыс болса, онда 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) қайда «N» - бұл енгізу массивінің өлшемі.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.

анықтамалық