Дархостҳо барои шумораи унсурҳои алоҳида дар зергурӯҳ


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Amazon Google Microsoft Oracle Uber
тартиботи ҳарбӣ Сегмент-дарахт Дарахт

Мо додаем асал шумораи бутун ва як қатор дархостҳо ва мо бояд шумораи ҳамаи унсурҳои фарқиятеро, ки дар доираи додашуда дорем, фаҳмем, дархост аз ду рақами чап ва рост иборат аст, ин диапазони додашуда мебошад, бо ин диапазони додашуда мо бояд шумораи унсурҳои фарқро пайдо кунед.

мисол

Қайд:

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

0, 4

1, 3

2, 4

Натиҷа:

4 3 2

Шарҳ:

Дар пурсиши аввал, шумораи бутунҳои алоҳида дар [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 дар индекси ташрифиAArray [a [i]] навсозӣ кунед.
  7. Танзими visitArray [a [i]] = i ва массиви binaryIndTree binaryIndTree -ро бо арзиши 1 дар индекси i навсозӣ кунед.
  8. Ҳисобкунакро ба 0 насб кунед ва ҳаракатро то он даме, ки ҳисобкунак камтар аз дархост бошад ва инчунин то он даме ки арзиши дурусти саволҳо ба i баробар аст.
  9. Барои индекси ҳар як дархостҳои объект, массиви индекси дархостҳоро ҳамчун фарқи арзиши дурусти дархостҳо ва арзиши чапи дархостҳоро навсозӣ кунед.
  10. Ҳама натиҷаҳоро барои ҳар як дархости муайяншуда чоп кунед.

Шарҳ

Мо массиви объектро тавре месозем, ки бо он массиви объект чап, рост ва индекс ё ​​шумораи дархостро пайваст кунем. Он гоҳ мо ин объекти дархостро тавре ҷобаҷо хоҳем кард, ки массиви дархостҳо бо тартиби афзоиши арзишҳои 'right' ҷобаҷогузорӣ кунад, маънои дархосте, ки арзиши камтарини 'right' дар навбати аввал гузошта мешавад.

Акнун, массиви эҷод кунед, ки binaryIndTree аст. Ҳама арзишҳои массивро бо 0 оғоз кунед, пас массиви андозаи max созед, ки он 1000001 мебошад. Ҳамаи қиматҳои ин массивро ба -1 ва массиви охирини натиҷаи дархости андоза оғоз намоед, зеро шумораи онҳо ҳамон баромади ҳамчун шумораи пурсишҳо. Арзиши ҳисобкунак бояд ба 0 таъин карда шавад. Ҳоло мо гашти массивро оғоз мекунем ва месанҷем, ки visitArray [arr [i]] = -1, агар он дуруст бошад, арзиши binaryIndTree -ро бо арзиши -1 навсозӣ кунед. Пас аз навсозӣ арзиши visitArray [arr [i]] -ро ба i баргардонед ва боз binaryIndTree -ро бо арзиши 1 нав кунед, ин бояд иҷро карда шавад, агар шарти боло дуруст бошад ё не.

Дар доираи ин ҳалқа, навсозии массивро оғоз кунед ва ин бояд то он даме, ки арзиши ҳисобкунак аз арзиши шумораи дархост камтар бошад, анҷом дода шавад. Массивҳои натиҷагириро бо фарқи саволҳои 'арзиши рост ва дархостҳо' бо арзиши чап навсозӣ кунед ва дар ҳар як нишондиҳанда навсозӣ кунед, фаромӯш накунед, вақте ки мо индексро бо шумораи дархостҳо эҷод мекунем. Ва арзиши ҳисобкунакро баланд бардоред. Ниҳоят, ҳамаи арзишҳоро дар массиви баромади чоп кунед.

татбиќи

Барномаи 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) ки дар "Н" андозаи массиви вуруд аст.

Мураккабии фазо

Эй (н) ки дар "Н" шумораи унсурҳои массив аст.

ишора