సుబారేలోని విభిన్న మూలకాల సంఖ్య కోసం ప్రశ్నలు


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది అమెజాన్ గూగుల్ మైక్రోసాఫ్ట్ ఒరాకిల్ ఉబెర్
అర్రే సెగ్మెంట్-ట్రీ ట్రీ

మేము ఒక ఇచ్చాము అమరిక పూర్ణాంకం మరియు అనేక ప్రశ్నలు మరియు ఇచ్చిన పరిధిలో మనకు ఉన్న అన్ని విభిన్న మూలకాల సంఖ్యను మనం కనుగొనవలసి ఉంది, ప్రశ్న ఎడమ మరియు కుడి రెండు సంఖ్యలను కలిగి ఉంటుంది, ఇది ఇచ్చిన పరిధి, ఈ ఇచ్చిన పరిధితో మనం కలిగి ఉండాలి విభిన్న అంశాల సంఖ్యను కనుగొనండి.

ఉదాహరణ

ఇన్పుట్:

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. శ్రేణి బైనరీఇండ్‌ట్రీని సృష్టించండి [].
  4. ఇచ్చిన శ్రేణిని దాటడం ప్రారంభించండి మరియు ఇచ్చిన ప్రశ్నలకు ఏకకాలంలో,
  5. సందర్శించిన అర్రే [a [i]] -1 అని తనిఖీ చేయండి.
  6. తప్పు అయితే, సందర్శించిన సూచిక వద్ద విలువ -1 తో బైనరీఇండ్‌ట్రీ శ్రేణిని నవీకరించండి [a [i]].
  7. విజిటెడ్అర్రే [a [i]] = i ని సెట్ చేసి, బైనరీఇండ్‌ట్రీ అర్రే బైనరీఇండ్‌ట్రీ శ్రేణిని ఇండెక్స్ i వద్ద విలువ 1 తో నవీకరించండి.
  8. కౌంటర్ 0 కి సెట్ చేయండి మరియు కౌంటర్ ప్రశ్న కంటే తక్కువగా ఉండే వరకు మరియు ప్రశ్నల సరైన విలువ i కి సమానంగా ఉండే వరకు ప్రయాణించండి.
  9. వస్తువు యొక్క ప్రతి ప్రశ్నల సూచిక కోసం, ప్రశ్నల యొక్క సరైన విలువ మరియు ప్రశ్నల ఎడమ విలువ యొక్క వ్యత్యాసంగా విలువ ప్రశ్న సూచికను శ్రేణి నవీకరించండి.
  10. నిర్వచించిన ప్రతి ప్రశ్నకు అన్ని ఫలితాలను ముద్రించండి.

వివరణ

మేము ఆబ్జెక్ట్ శ్రేణిని తయారు చేయబోతున్నాము, ఆ వస్తువు శ్రేణితో మనం ఎడమ, కుడి మరియు సూచిక లేదా ప్రశ్న సంఖ్యను లింక్ చేయబోతున్నాము. అప్పుడు మేము ఆ ప్రశ్న వస్తువును క్రమబద్ధీకరించబోతున్నాము, అంటే ప్రశ్నలు 'కుడి' విలువల యొక్క ఆరోహణ క్రమంలో క్రమబద్ధీకరించబడతాయి, అంటే 'కుడి' యొక్క కనీస విలువను కలిగి ఉన్న ప్రశ్న మొదట క్రమంలో వస్తుంది.

ఇప్పుడు, బైనరీఇండ్‌ట్రీ అనే శ్రేణిని సృష్టించండి. శ్రేణి యొక్క అన్ని విలువలను 0 తో ప్రారంభించండి, ఆపై 1000001 పరిమాణ పరిమాణం యొక్క శ్రేణిని సృష్టించండి. ఈ శ్రేణి యొక్క అన్ని విలువలను -1 కు ప్రారంభించండి మరియు పరిమాణ ప్రశ్న యొక్క అవుట్పుట్ యొక్క చివరి శ్రేణిని ప్రారంభించండి, ఎందుకంటే అదే సంఖ్యలో ఉంటుంది ప్రశ్నల సంఖ్యగా అవుట్పుట్. కౌంటర్ యొక్క విలువను 0 గా సెట్ చేయాలి. ఇప్పుడు మనం శ్రేణిని దాటడం మొదలుపెట్టాము మరియు సందర్శించిన అర్రే [arr [i]] = -1, అది నిజమని తేలితే బైనరీఇండ్‌ట్రీ విలువను విలువ -1 తో నవీకరించండి. అప్‌డేట్ చేసిన తర్వాత విలువ అర్రే [అర్ర్ [i]] ను i కు, మరియు బైనరీఇండ్‌ట్రీని విలువ 1 తో మళ్ళీ అప్‌డేట్ చేయండి, పై పరిస్థితి నిజమా కాదా అని ఇది చేయాలి.

ఈ లూప్‌లో, శ్రేణిని నవీకరించడం ప్రారంభించండి మరియు కౌంటర్ విలువ ప్రశ్న సంఖ్య కంటే తక్కువగా ఉండే వరకు ఇది చేయాలి, q. ప్రతి సూచికలో ప్రశ్నల యొక్క కుడి విలువ మరియు ప్రశ్నల ఎడమ విలువ మరియు నవీకరణ యొక్క వ్యత్యాసంతో అవుట్పుట్ శ్రేణిని నవీకరించండి, మేము సూచికను ప్రశ్నల సంఖ్యతో సమానంగా సృష్టించినప్పుడు గుర్తుంచుకోండి. మరియు కౌంటర్ విలువను పెంచండి. చివరగా, అవుట్పుట్ శ్రేణిలోని అన్ని విలువలను ముద్రించండి.

అమలు

సబ్‌రేలో విభిన్న మూలకాల సంఖ్య కోసం ప్రశ్నల కోసం సి ++ ప్రోగ్రామ్

#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

సుబారేలోని విభిన్న మూలకాల సంఖ్య కోసం ప్రశ్నలకు సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (ప్రశ్నలు * లాగ్ n)  (ఇక్కడ  “N” ఇన్పుట్ శ్రేణి యొక్క పరిమాణం.

అంతరిక్ష సంక్లిష్టత

పై) (ఇక్కడ “N” శ్రేణిలోని మూలకాల సంఖ్య.

సూచన