Заявки за брой отделни елементи в подмасив  


Ниво на трудност Трудно
Често задавани в Амазонка Google Microsoft Оракул Uber
Array Сегментно дърво Дърво

Дадохме масив на цяло число и редица заявки и трябва да разберем броя на всички отделни елементи, които имаме в рамките на дадения диапазон, заявката се състои от две числа вляво и вдясно, това е даденият диапазон, с този даден диапазон трябва да разберете броя на отделните елементи.

Пример  

Вход:

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. проверете дали visitArray [a [i]] е -1.
  6. Ако е невярно, актуализирайте масива binaryIndTree със стойност -1 в индекса visitArray [a [i]].
  7. Задайте visitArray [a [i]] = i и актуализирайте масива binaryIndTree binaryIndTree със стойност 1 при индекс i.
  8. Задайте брояч на 0 и започнете да обхождате, докато броячът е по-малък от никой на заявката, а също така, докато дясната стойност на заявките е равна на i.
  9. За всеки индекс на заявките на обекта масив актуализирайте индекса на заявката за стойност като разликата в дясната стойност на заявките и лявата стойност на заявките.
  10. Отпечатайте всички резултати за всяка дефинирана заявка.
Вижте също
Пренаредете масив така, че „arr [j]“ да стане „i“, ако „arr [i]“ е „j“

Обяснение  

Ще направим масив от обекти, така че с този масив от обекти да свържем лявото, дясното и индекса или броя на заявката. След това ще сортираме този обект на заявка, така че масивът за заявки да сортира във възходящ ред на „правилните“ стойности, означава, че заявката, която има най-малката стойност на „правилната“ воля, е на първо място по ред.

Сега създайте масив, който е binaryIndTree. Инициализирайте всички стойности на масива с 0, след това създайте масив с размер max, който е 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) където "н" е размерът на входния масив.

Вижте също
Съвпадение на низовете в решение с масив Leetcode

Сложност на пространството

О (п) където "н" е броят на елементите в масива.

препратка