მოთხოვნები გამოყოფილი მასალის ცალკეული ელემენტების რაოდენობის შესახებ


Რთული ტური Hard
ხშირად ეკითხებიან Amazon Google microsoft Oracle 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. შეამოწმეთ, თუ მონახულებული მასივი [a [i]] არის -1.
  6. თუ ცრუა, განაახლეთ binaryIndTree მასივი -1 მნიშვნელობით, რომელიც მოინახულა indexArray [a [i]].
  7. დააყენეთ visitArray [a [i]] = i და განაახლეთ binaryIndTree მასივი binaryIndTree მასივი მნიშვნელობით 1 ინდექსში.
  8. დააყენეთ მრიცხველი 0-ზე და დაიწყეთ გადაკვეთა, სანამ მრიცხველი არ იქნება მოთხოვნაზე ნაკლები და ასევე, სანამ მოთხოვნების სწორი მნიშვნელობა არ იქნება i.
  9. ობიექტის თითოეული მოთხოვნის ინდექსისთვის, მასივში განაახლეთ მნიშვნელობის მოთხოვნის ინდექსი, როგორც სხვაობის მოთხოვნების სწორი მნიშვნელობა და მოთხოვნების მარცხენა მნიშვნელობა.
  10. ამობეჭდეთ ყველა შედეგი თითოეული განსაზღვრული მოთხოვნისთვის.

განმარტება

ჩვენ ვაპირებთ ობიექტის მასივის შექმნას ისე, რომ ამ ობიექტის მასივთან ჩვენ ვაკავშირებთ მოთხოვნის მარცხენა, მარჯვენა და ინდექსის ან რაოდენობის დაკავშირებას. შემდეგ ჩვენ ვაპირებთ დავალაგოთ შეკითხვის ობიექტი ისე, რომ მოთხოვნების მასივი დალაგდეს "სწორი" მნიშვნელობების ზრდადი თანმიმდევრობით, ნიშნავს მოთხოვნას, რომელსაც აქვს "სწორი" ნების ნაკლები მნიშვნელობა.

ახლა, შექმენით მასივი, რომელიც არის binaryIndTree. მასივის ყველა მნიშვნელობის ინიცირება 0-ით, შემდეგ კი შევქმნათ ზომის მაქსიმალური მასივი, რომელიც არის 1000001. ამ მასივის ყველა მნიშვნელობის ინიცირება -1-ზე და ზომის მოთხოვნის გამომავალი ბოლო მასივზე, რადგან იქ იგივე რაოდენობის იქნება გამომავალი, როგორც მოთხოვნების რაოდენობა. მრიცხველის მნიშვნელობა უნდა იყოს 0 დადგენილი. ახლა ჩვენ ვიწყებთ მასივის გადახედვას და ვამოწმებთ, თუ visitArray [arr [i]] = -1, თუ აღმოჩნდა მართალი, განაახლეთ binaryIndTree მნიშვნელობა -1 მნიშვნელობით. განახლების შემდეგ მნიშვნელობამ მოინახულა Arrray [arr [i]] to 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) სადაც "ნ" არის შეყვანის მასივის ზომა.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

Reference