උපසිරැසියක ඇති විශේෂිත මූලද්‍රව්‍ය ගණන සඳහා විමසුම්


දුෂ්කරතා මට්ටම Hard
නිතර අසනු ලැබේ ඇමේසන් ගූගල් මයික්රොසොෆ්ට් ඔරකල් 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. සංචාරය කළ අරාව [a [i]] -1 දැයි පරීක්ෂා කරන්න.
  6. අසත්‍ය නම්, පිවිසුණු දර්ශකයේ -1 අගය සහිත ද්විමය ඉන්ඩ්‍රී අරා යාවත්කාලීන කරන්න [a [i]].
  7. VisitArray [a [i]] = i ලෙස සකසා ද්විමයඉන්ඩ්ට්‍රී අරා ද්විමයඉන්ඩ්ට්‍රී අරා 1 දර්ශකයේ අගය XNUMX සමඟ යාවත්කාලීන කරන්න.
  8. කවුන්ටරය 0 ට සකසා, කවුන්ටරය විමසුමට වඩා අඩු වන තෙක්ත්, විමසුම් වල නිවැරදි අගය i ට සමාන වන තෙක්ත් ගමන් කරන්න.
  9. වස්තුවේ එක් එක් විමසුම් දර්ශකය සඳහා, අරාව මඟින් විමසුම් වල නිවැරදි අගය සහ විමසුම් වල වම් අගයෙහි වෙනස ලෙස අගය විමසුම් දර්ශකය යාවත්කාලීන කරන්න.
  10. අර්ථ දක්වා ඇති එක් එක් විමසුම සඳහා සියලු ප්‍රති results ල මුද්‍රණය කරන්න.

පැහැදිලි කිරීම

අපි වස්තු අරාව සෑදීමට යන්නේ එම වස්තු අරාව සමඟ අපි වම්, දකුණ සහ දර්ශකය හෝ විමසුම් ගණන සම්බන්ධ කිරීමට ය. එවිට අපි එම විමසුම් වස්තුව වර්ග කිරීමට යන්නේ, විමසුම් අරාව 'හරි' අගයන්හි නැගීමේ අනුපිළිවෙලට වර්ග කිරීමෙනි, එයින් අදහස් කරන්නේ 'හරි' හි අවම අගය ඇති විමසුම පළමුව පිළිවෙලට පැමිණෙනු ඇති බවයි.

දැන්, binaryIndTree නම් අරාවක් සාදන්න. අරාවෙහි සියලු අගයන් 0 සමඟ ආරම්භ කරන්න, ඉන්පසු 1000001 ප්‍රමාණයේ උපරිම අරාවක් සාදන්න. මෙම අරාවෙහි සියලු අගයන් -1 දක්වා ආරම්භ කරන්න සහ ප්‍රමාණ විමසුමේ නිමැවුමේ අවසාන අරාව, මන්ද එකම සංඛ්‍යාවක් ඇති නිසාය විමසුම් ගණන ලෙස ප්‍රතිදානය. කවුන්ටරයේ අගය 0 ලෙස සැකසිය යුතුය. දැන් අපි අරාව හරහා ගමන් කිරීම ආරම්භ කර, සංචාරය කළ අරා [arr [i]] = -1, එය සත්‍යයක් බව සොයා ගන්නේ නම්, ද්විමය ඉන්ඩ්‍රී හි අගය -1 අගය සමඟ යාවත්කාලීන කරන්න. යාවත්කාලීනයෙන් පසුව ඇරේ [arr [i]] අගය i වෙත ගෙන, ද්විමයඉන්ඩ්ට්‍රී 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

උපසිරැසියක ඇති විශේෂිත මූලද්‍රව්‍ය ගණන සඳහා විමසීම් සඳහා සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (විමසුම් * ලොග් එන්) එහිදී “N” යනු ආදාන අරාවේ ප්‍රමාණයයි.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

විමර්ශන