सबर्रे में डिस्टिक्ट एलिमेंट्स की संख्या के लिए प्रश्न


कठिनाई स्तर कठिन
में अक्सर पूछा वीरांगना गूगल माइक्रोसॉफ्ट ओरेकल Uber
ऐरे खंड-वृक्ष पेड़

हमने ए सरणी पूर्णांक और प्रश्नों की एक संख्या और हमें दिए गए सीमा के भीतर हमारे पास मौजूद सभी अलग-अलग तत्वों की संख्या का पता लगाना है, क्वेरी में दो नंबर बाएं और दाएं हैं, यह दी गई सीमा है, इस दी गई सीमा के साथ हमें विभिन्न तत्वों की संख्या ज्ञात कीजिए।

उदाहरण

इनपुट:

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. देखें कि क्या दौराअरे [[एक]] -1 है।
  6. यदि गलत है, तो बाइनरीइंडट्री एरे को वैल्यू -1 पर इंडेक्स विज़िट के साथ अपडेट करें।
  7. विज़िटअअर्रे सेट करें [a [i] = i और बाइनरीइंड्री एरे को बाइनरीइंड्री एरी से अपडेट करें। इंडेक्स १ पर मान १ के साथ।
  8. काउंटर को 0 पर सेट करें, और तब तक चलना शुरू करें जब तक काउंटर क्वेरी से कम न हो और जब तक प्रश्न सही मूल्य के बराबर न हो।
  9. ऑब्जेक्ट के प्रत्येक क्वेरीज़ इंडेक्स के लिए, ऐरे वैल्यू क्वेरी इंडेक्स को क्वेरीज़ के राइट वैल्यू और प्रश्नों के लेफ्ट वैल्यू के अंतर के रूप में अपडेट करते हैं।
  10. परिभाषित प्रत्येक क्वेरी के लिए सभी परिणाम प्रिंट करें।

व्याख्या

हम एक ऑब्जेक्ट ऐरे को बनाने जा रहे हैं, उस ऑब्जेक्ट एरे के साथ हम लेफ्ट, राइट और इंडेक्स या क्वेरी की संख्या को लिंक करने जा रहे हैं। फिर हम उस क्वेरी ऑब्जेक्ट को सॉर्ट करने जा रहे हैं जिससे क्वेरीज़ 'सही' मानों के आरोही क्रम में क्रमबद्ध हो जाती हैं, जिसका अर्थ है कि 'राइट' का कम से कम मान पहले क्रम में आएगा।

अब, एक सरणी बनाएं जो बाइनरीइंडट्री है। सरणी के सभी मानों को 0 के साथ प्रारंभ करें, फिर आकार की एक सरणी बनाएं, जो 1000001 है। इस सरणी के सभी मानों को प्रारंभ करें -1 और आकार क्वेरी के आउटपुट के अंतिम सरणी, क्योंकि समान संख्या होगी प्रश्नों की संख्या के रूप में आउटपुट। काउंटर के मान को 0. पर सेट किया जाना चाहिए। अब हम एरे को ट्रेस करना शुरू करते हैं और देखें कि एअरर्रे [गिरफ्तार [i] = = -1 है या नहीं, अगर यह सही पाया जाता है तो वैल्यू -1 के साथ बाइनरीइंडट्री के मान को अपडेट करें। अद्यतन के बाद मान का दौरा किया गया है [गिरफ्तार करें] [i] से i तक, और फिर से बाइनरीइंड्री को मान 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

सबर्रे में विकृत तत्वों की संख्या के लिए जावा कार्यक्रम

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

एक सबर्रे में विकृत तत्वों की संख्या के लिए क्वेरी के लिए जटिलता विश्लेषण

समय जटिलता

ओ (प्रश्न * लॉग एन) जहां "N" इनपुट सरणी का आकार है।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है।

संदर्भ