پرس و جو برای تعداد عناصر مجزا در یک زیر مجموعه


سطح دشواری سخت
اغلب در آمازون گوگل مایکروسافت وحی حال بارگذاری
صف درخت بخش درخت

ما داده ایم صف از عدد صحیح و تعدادی پرس و جو باید بدانیم که تعداد عناصر متمایز موجود در محدوده داده شده چیست ، پرس و جو از دو عدد چپ و راست تشکیل شده است ، این محدوده داده شده است ، با این دامنه داده شده باید تعداد عناصر مجزا را دریابید.

مثال

ورودی:

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

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 است (XNUMX ، XNUMX).

تعداد تمام عناصر متمایز موجود را در محدوده مشخص شده دریابید ،

الگوریتم

  1. آرایه شی را ایجاد کرده و با هر موقعیت مقادیر را به صورت چپ ، راست و شاخص مربوط به هر کدام علامت گذاری کنید هدف.
  2. آرایه پرس و جو را با توجه به مقدار صحیح داده شده به عنوان محدوده مرتب کنید.
  3. یک آرایه binaryIndTree ایجاد کنید].
  4. شروع به آرایه داده شده و به طور همزمان پرس و جوهای داده شده ،
  5. بررسی کنید آیا آرایه بازدید شده [a [i]] -1 است.
  6. اگر نادرست باشد ، آرایه binaryIndTree را با مقدار -1 در فهرست بازدید شدهArray [a [i]] به روز کنید.
  7. visitArray [a [i]] = i را تنظیم کنید و آرایه binaryIndTree binaryIndTree را با مقدار 1 در شاخص i به روز کنید.
  8. شمارنده را برابر 0 قرار داده و پیمایش را شروع کنید تا شمارنده کمتر از پرس و جو باشد و همچنین تا زمانی که مقدار درست پرس و جو برابر با i شود.
  9. برای هر نمایه نمایش داده شده از شی ، آرایه شاخص پرس و جو مقدار را به عنوان تفاوت مقدار سمت راست نمایش داده شده و مقدار باقی مانده درخواست ، به روز می کند.
  10. همه نتایج را برای هر پرسش تعریف شده چاپ کنید.

توضیح

ما می خواهیم یک آرایه شی به گونه ای بسازیم که با آن آرایه شی object ، چپ ، راست و شاخص یا تعداد پرس و جو را پیوند دهیم. سپس ما قصد داریم آن شی qu پرس و جو را مرتب کنیم به گونه ای که آرایه نمایشگرها به ترتیب صعودی مقادیر 'درست' مرتب شوند ، به این معنی که پرسشی که کمترین مقدار اراده 'را دارد' در مرتبه اول قرار دارد.

اکنون یک آرایه ایجاد کنید که binaryIndTree باشد. تمام مقادیر آرایه را با 0 مقداردهی اولیه کنید ، سپس یک آرایه با اندازه حداکثر که 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

برنامه جاوا برای نمایشگرهای تعداد عناصر مجزا در یک زیر مجموعه

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

تجزیه و تحلیل پیچیدگی برای سeriesالات مربوط به تعداد عناصر مجزا در یک زیر مجموعه

پیچیدگی زمان

O (نمایش داده شد * ورود به سیستم) جایی که "n" اندازه آرایه ورودی است.

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است.

ارجاع