ಸಬ್‌ರೇನಲ್ಲಿನ ವಿಶಿಷ್ಟ ಅಂಶಗಳ ಸಂಖ್ಯೆಯ ಪ್ರಶ್ನೆಗಳು


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಒರಾಕಲ್ ಉಬರ್
ಅರೇ ವಿಭಾಗ-ಮರ ಮರ

ನಾವು ಒಂದು ನೀಡಿದ್ದೇವೆ ಸರಣಿ ಪೂರ್ಣಾಂಕ ಮತ್ತು ಹಲವಾರು ಪ್ರಶ್ನೆಗಳು ಮತ್ತು ನಿರ್ದಿಷ್ಟ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ನಾವು ಹೊಂದಿರುವ ಎಲ್ಲಾ ವಿಭಿನ್ನ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ, ಪ್ರಶ್ನೆಯು ಎಡ ಮತ್ತು ಬಲಕ್ಕೆ ಎರಡು ಸಂಖ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿದೆ, ಇದು ಕೊಟ್ಟಿರುವ ಶ್ರೇಣಿ, ಈ ಶ್ರೇಣಿಯೊಂದಿಗೆ ನಾವು ಮಾಡಬೇಕಾಗಿದೆ ವಿಭಿನ್ನ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ.

ಉದಾಹರಣೆ

ಇನ್ಪುಟ್:

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 ಕ್ಕೆ ಪ್ರಾರಂಭಿಸಿ ಮತ್ತು ಗಾತ್ರದ ಪ್ರಶ್ನೆಯ output ಟ್‌ಪುಟ್‌ನ ಕೊನೆಯ ಶ್ರೇಣಿಯನ್ನು ಪ್ರಾರಂಭಿಸಿ, ಏಕೆಂದರೆ ಅದೇ ಸಂಖ್ಯೆಯ ಸಂಖ್ಯೆ ಇರುತ್ತದೆ ಪ್ರಶ್ನೆಗಳ ಸಂಖ್ಯೆಯಂತೆ output ಟ್‌ಪುಟ್. ಕೌಂಟರ್‌ನ ಮೌಲ್ಯವನ್ನು 0 ಗೆ ಹೊಂದಿಸಬೇಕು. ಈಗ ನಾವು ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗಲು ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ ಮತ್ತು ಭೇಟಿ ನೀಡಿದ ಅರೇ [arr [i]] = -1, ಅದು ನಿಜವೆಂದು ಕಂಡುಬಂದಲ್ಲಿ ಬೈನರಿಇಂಡ್‌ಟ್ರೀ ಮೌಲ್ಯವನ್ನು ಮೌಲ್ಯ -1 ನೊಂದಿಗೆ ನವೀಕರಿಸಿ. ನವೀಕರಣದ ನಂತರ ಮೌಲ್ಯಕ್ಕೆ ಭೇಟಿ ನೀಡಿದ ಅರೇ [ಅರ್ [i]] ಅನ್ನು ಮತ್ತೆ, ಮತ್ತು ಬೈನರಿಇಂಡ್‌ಟ್ರೀ ಅನ್ನು 1 ಮೌಲ್ಯದೊಂದಿಗೆ ನವೀಕರಿಸಿ, ಮೇಲಿನ ಷರತ್ತು ನಿಜವೋ ಅಥವಾ ಇಲ್ಲವೋ ಎಂದು ಇದನ್ನು ಮಾಡಬೇಕು.

ಈ ಲೂಪ್ ಒಳಗೆ, ರಚನೆಯನ್ನು ನವೀಕರಿಸಲು ಪ್ರಾರಂಭಿಸಿ ಮತ್ತು ಕೌಂಟರ್‌ನ ಮೌಲ್ಯವು ಪ್ರಶ್ನೆಯ ಸಂಖ್ಯೆಯ ಮೌಲ್ಯಕ್ಕಿಂತ ಕಡಿಮೆಯಾಗುವವರೆಗೆ ಇದನ್ನು ಮಾಡಬೇಕು, q. ಪ್ರತಿ ಸೂಚ್ಯಂಕದಲ್ಲಿ ಪ್ರಶ್ನೆಗಳ ಸರಿಯಾದ ಮೌಲ್ಯ ಮತ್ತು ಪ್ರಶ್ನೆಗಳ ಎಡ ಮೌಲ್ಯ ಮತ್ತು ನವೀಕರಣದ ವ್ಯತ್ಯಾಸದೊಂದಿಗೆ array ಟ್‌ಪುಟ್ ಶ್ರೇಣಿಯನ್ನು ನವೀಕರಿಸಿ, ನಾವು ಸೂಚ್ಯಂಕವನ್ನು ಪ್ರಶ್ನೆಗಳ ಸಂಖ್ಯೆಯಂತೆಯೇ ರಚಿಸಿದಾಗ ನೆನಪಿಡಿ. ಮತ್ತು ಕೌಂಟರ್ ಮೌಲ್ಯವನ್ನು ಹೆಚ್ಚಿಸಿ. ಅಂತಿಮವಾಗಿ, values ​​ಟ್‌ಪುಟ್ ಶ್ರೇಣಿಯಲ್ಲಿನ ಎಲ್ಲಾ ಮೌಲ್ಯಗಳನ್ನು ಮುದ್ರಿಸಿ.

ಅನುಷ್ಠಾನ

ಸಬ್‌ರೇನಲ್ಲಿನ ವಿಶಿಷ್ಟ ಅಂಶಗಳ ಸಂಖ್ಯೆಗಾಗಿ ಪ್ರಶ್ನೆಗಳಿಗಾಗಿ ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ಸಬ್‌ಅರೇನಲ್ಲಿನ ವಿಶಿಷ್ಟ ಅಂಶಗಳ ಸಂಖ್ಯೆಯ ಪ್ರಶ್ನೆಗಳಿಗೆ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಪ್ರಶ್ನೆಗಳು * ಲಾಗ್ ಎನ್) ಅಲ್ಲಿ “ಎನ್” ಇನ್ಪುಟ್ ರಚನೆಯ ಗಾತ್ರ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ.

ರೆಫರೆನ್ಸ್