Ենթավանդակի հստակ տարրերի քանակի հարցումներ


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Amazon Google Microsoft Պատգամախոս Uber
Դասավորություն Հատված-ծառ ծառ

Մենք տվել ենք դասավորություն ամբողջ թվերի և մի շարք հարցումների, և մենք պետք է պարզենք տրված տիրույթում առկա բոլոր հստակ տարրերի քանակը, հարցումը բաղկացած է ձախ և աջ երկու թվերից, սա տվյալ տիրույթն է, և տվյալ տվյալ տիրույթով մենք պետք է պարզել հստակ տարրերի քանակը:

Օրինակ

Մուտք:

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

0, 4

1, 3

2, 4

Արդյունք:

4 3 2

Բացատրությունը.

Առաջին հարցումում [0… 4] -ում հստակ ամբողջ թվերի թիվը 4 է (4, 3, 2,1): Երկրորդ հարցումում [1..3] -ում հստակ ամբողջ թվերի թիվը 3 է (4, 3,1): Երրորդ հարցումում [2..4] -ում հստակ ամբողջ թվերի քանակը 2 է (1, 4):

պարզել տրված տիրույթում առկա բոլոր հստակ տարրերի քանակը,

Ալգորիթմ

  1. Կազմիր առարկայի զանգվածը և յուրաքանչյուր դիրքի հետ նշիր արժեքները ձախ, աջ և յուրաքանչյուրի հետ կապված ցուցիչ օբյեկտ.
  2. Տեսակավորել հարցման զանգվածը `որպես միջակայք տրված ճիշտ արժեքի համեմատ:
  3. Ստեղծեք զանգված binaryIndTree []:
  4. Սկսեք անցնել տրված զանգվածը և միաժամանակ տրված հարցումները,
  5. ստուգեք այցելված Array- ի [a [i]] - ը -1:
  6. Եթե ​​կեղծ է, թարմացրեք binaryIndTree զանգվածը -1 արժեքով ՝ այցելված ցուցակում [a [i]]:
  7. Սահմանեք visitArray [a [i]] = i և թարմացրեք binaryIndTree զանգվածի binaryIndTree զանգվածը 1 արժեքով i ինդեքսում:
  8. Սահմանեք 0-ը և սկսեք շրջել մինչև, երբ հաշվիչը պակաս լինի հարցման բացակայությունից, ինչպես նաև մինչ հարցումների ճիշտ արժեքը հավասար լինի i- ին:
  9. Օբյեկտի յուրաքանչյուր հարցումի ինդեքսի համար զանգվածը թարմացնում է արժեքի հարցման ինդեքսը ՝ որպես հարցումների ճիշտ արժեքի և հարցումների ձախ արժեքի տարբերություն:
  10. Տպեք բոլոր արդյունքները սահմանված յուրաքանչյուր հարցման համար:

բացատրություն

Մենք պատրաստվում ենք օբյեկտի զանգված ստեղծել այնպես, որ այդ օբյեկտի զանգվածի հետ կապենք հարցման ձախ, աջ և ինդեքսը կամ քանակը: Այդ դեպքում մենք տեսակավորելու ենք այդ հարցման օբյեկտը այնպես, որ հարցումների զանգվածը տեսակավորվի ըստ «ճիշտ» արժեքների աճման կարգի, նշանակում է, որ «ճիշտ» կամքի նվազագույն արժեք ունեցող հարցումն առաջին հերթին դասվում է:

Այժմ ստեղծեք զանգված, որը binaryIndTree է: Rayանգի բոլոր արժեքները սկզբնավորիր 0-ով, ապա ստեղծիր max չափի զանգված, որը 1000001 է: Նախաձեռնիր այս զանգվածի բոլոր արժեքները -1 և չափի հարցման ելքի վերջին զանգված, քանի որ այնտեղ կլինի նույն քանակի արդյունքը ՝ որպես հարցումների քանակ: Հաշվիչի արժեքը պետք է դրվի 0: Այժմ մենք սկսում ենք զանգվածը զննել և ստուգել, ​​արդյոք այցելված Array [arr [i]] = -1, եթե պարզվել է, որ ճիշտ է, ապա binaryIndTree- ի արժեքը թարմացրեք -1 արժեքով: Թարմացնելուց հետո արժեքը այցելել է Array [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

Ենթանկարի հստակ տարրերի քանակի հարցումների բարդության վերլուծություն

Timeամանակի բարդություն

O (հարցումներ * տեղեկամատյան n) որտեղ «Ն» մուտքային զանգվածի չափն է:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Մանրամասն