दायरा न्यूनतम क्वेरी (वर्ग रूट अपघटन र विरल टेबल)


कठिनाई तह हार्ड
बारम्बार सोधिन्छ अमेजन एप्पल गुगल
एरे खण्ड-रूख

दायरा न्यूनतम क्वेरी समस्यामा हामीले क्वेरी र पूर्ण संख्या दिएका छौं array। प्रत्येक क्वेरीमा दायरा प्रत्येक दायराको लागि बाँया र दाँया अनुक्रमणिकाको रूपमा हुन्छ। दिइएको कार्य भनेको दायरा भित्र रहेको सबै संख्याको न्यूनतम निर्धारण गर्नु हो।

उदाहरणका

इनपुट:

एर [] = {१,,,,, २,,,,,,,}}

प्रश्न = {(०,)), (१,)), (,,))}

उत्पादन:

2 5 6

व्याख्या:

२ दायरा संख्या बीचमा न्यूनतम हो - २,,,,,,, १ 2,}}

The दायरा संख्याहरूमध्ये 5,,,,,, १} among बीचमा न्यूनतम हो

The दायरा संख्याहरूको बीचमा न्यूनतम हो {,, १,, among, 6, १०}

दायरा न्यूनतम क्वेरी (वर्ग रूट अपघटन र विरल टेबल)

अल्गोरिदम

  1. एउटा २ डी एरे सिर्जना गर्नुहोस् र यसलाई निर्माण गर्नुहोस्। त्यसको लागि ० अंकित गर्नुहोस्th प्रत्येक प row्क्तिको स्तम्भ यसको प row्क्ति अनुक्रमणिका मानको रूपमा।
  2. एर्रे ट्रान्सवर्स गर्नुहोस्, र जाँच गर्नुहोस् कि i, j-1 मा एरेहिंग एर्रे i + 2 मा खोज एरेभन्दा कम छ।j-1, j-1, यदि सहि छ भने i, j मा लुकअप एर्रे रूपमा i, j-1 मा लुकअप एरे अपडेट गर्नुहोस्।
  3. अन्यथा i + j मा लुकअप एरे अपडेट गर्नुहोस्j-1, j-1
  4. प्रत्येक दिइएको क्वेरीको लागि, क्वेरीको बाँया र दायाँ दायरा प्राप्त गर्नुहोस्, दायाँ-बायाँ + १ को लग मान प्राप्त गर्नुहोस् र जाँच गर्नुहोस् कि बायाँ, j मा लुकअपको एरे बराबर भन्दा कम छ दायाँ - २ मा खोजको एरे बराबर भन्दा कम छ।j +१, j, तब दायाँ - २ मा खोजको एरेको रूपमा मान फिर्ता गर्नुहोस्j + १, j
  5. फर्काइएको मान प्रिन्ट गर्नुहोस्

दायरा न्यूनतम प्रश्नका लागि स्पष्टीकरण (वर्ग रूट अपघटन र विरल टेबल)

हामीले एउटा पूर्णा ar्क एरे र दायरा क्वेरी दियौं, हामीले सबै इन्टिजर मानहरू बीच न्यूनतम मान पत्ता लगाउन र त्यो मान फिर्ता गर्न सोधेका छौं, त्यसका लागि हामी लुकअप एरे निर्माण गर्नेछौं। समाधानलाई n खाली स्थानको वर्गमूल मात्र चाहिन्छ तर sqrt (n) समय खान्छ, जबकि प्रत्येक दिइएको क्वेरीको लागि, यसले स्थिर समय लिन्छ तर अतिरिक्त ठाउँ लिन्छ। यो विचारलाई हामी अगाडि राख्नेछौं साइज २ को सबभर्रेमा सबै सम्भव न्यूनतम मानहरू निर्धारण गर्नj जहाँ j एन को लग गर्न सक्नुहुन्छ।

हामी एक लुकअप तालिका निर्माण गर्नेछौं, यसको लागि हामी लुकअप एर्रे प्रयोग गर्नेछौं। एरमा लुप अपको निर्माणमा, i मा प्रत्येक खोजको लागि, i मा २ सम्म न्यूनतम मानहरू समात्छ।J। I, j मा खोज एर्रेले एर्रेको प्रत्येक मानमा मानहरूको अनुक्रमणिका होल्ड गर्नेछ। एर्रेको माध्यमबाट ट्र्याभिंग गर्ने क्रममा, हामी कुनै पनि सम्भावित आकारको दायराको लागि न्यूनतम मान २ पावर जेमा बढाइएको छ। यस कारणले गर्दा, हामी दिईएको दायरामा सम्भावित मान फेला पार्न सक्षम हुनेछौं।

कुनै दिईएको दायरा क्वेरीका लागि, हामी २ को शक्तिको रूपमा दायरा प्रयोग गर्छौं। दायाँ-बायाँ + १ को फरकको लग पत्ता लगाउन हामी दायरा मानहरू प्रयोग गर्नेछौं। त्यसपछि हामी बायाँ, j मा खोज्ने एरे तुलना गर्नेछौं। दायाँको एर्रे भन्दा सानो छ - २j + १, j, यदि कन्डिसन सहि फेला पर्‍यो भने बाँयाको लुकमा एर्रेको मान फिर्ता गर्नुहोस्, j, अन्यलाई दायाँको लुकमा एरे फिर्ता गर्नुहोस् - २j + १, j यो आवश्यक उत्तर हुनेछ।

कार्यान्वयन

C ++ दायरा न्यूनतम क्वेरीका लागि प्रोग्राम (वर्ग रूट अपघटन र विरल टेबल)

#include<iostream>
#include<math.h>

using namespace std;

#define MAX 500

int lookup[MAX][MAX];

struct Query
{
    int Left, Right;
};

void buildLookup(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        lookup[i][0] = i;
    for (int j=1; (1<<j)<=n; j++)
    {
        for (int i=0; (i+(1<<j)-1) < n; i++)
        {
            if (arr[lookup[i][j-1]] < arr[lookup[i + (1<<(j-1))][j-1]])
                lookup[i][j] = lookup[i][j-1];
            else
                lookup[i][j] = lookup[i + (1 << (j-1))][j-1];
        }
    }
}

int solveQuery(int arr[], int Left, int Right)
{
    int j = (int)log2(Right - Left + 1);

    if (arr[lookup[Left][j]] <= arr[lookup[Right - (1 << j) + 1][j]])
        return arr[lookup[Left][j]];

    else return arr[lookup[Right - (1<<j) + 1][j]];
}

void getMinimumNumber(int arr[], int n, Query q[], int m)
{
    for (int i = 0; i < m; i++)
    {
        int Left = q[i].Left, Right = q[i].Right;
        cout <<"Minimum value between ["<<Left<<", "<<Right<<"] is:"<< solveQuery(arr, Left, Right) << endl;
    }
}

int main()
{
    int a[] = {2,5,8,6,13,9,7,10};
    int n = sizeof(a)/sizeof(a[0]);
    Query q[] = {{0, 5}, {1, 4}, {3, 7}};
    int m = sizeof(q)/sizeof(q[0]);

    buildLookup(a, n);
    getMinimumNumber(a, n, q, m);
    return 0;
}
Minimum value between [0, 5] is:2
Minimum value between [1, 4] is:5
Minimum value between [3, 7] is:6

दायरा न्यूनतम क्वेरीका लागि जाभा कार्यक्रम (वर्ग रूट अपघटन र विरल टेबल)

class MinimumNumberQuery
{
    static int MAX = 500;

    static int [][]lookup = new int[MAX][MAX];

    static class Query
    {
        int Left, Right;

        public Query(int Left, int Right)
        {
            this.Left = Left;
            this.Right = Right;
        }
    }
    
    static void	buildLookup(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            lookup[i][0] = i;

        for (int j = 1; (1 << j) <= n; j++)
        {
            for (int i = 0; (i + (1 << j) - 1) < n; i++)
            {
                if (arr[lookup[i][j - 1]] < arr[lookup[i + (1 << (j - 1))][j - 1]])
                    lookup[i][j] = lookup[i][j - 1];
                else
                    lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1];
            }
        }
    }
    
    static int solveQuery(int arr[], int Left, int Right)
    {
        int j = (int)Math.log(Right - Left + 1);

        if (arr[lookup[Left][j]] <= arr[lookup[Right - (1 << j) + 1][j]])
            return arr[lookup[Left][j]];

        else return arr[lookup[Right - (1<<j) + 1][j]];
    }
    
    static void getMinimumNumber(int arr[], int n, Query q[], int m)
    {
        for (int i = 0; i < m; i++)
        {
            int Left = q[i].Left, Right = q[i].Right;

            System.out.println("Minimum of [" + Left + ", " + Right +
                               "] is " + solveQuery(arr, Left, Right));
        }
    }
    
    public static void main(String[] args)
    {
        int arr[] = {2,5,8,6,13,9,7,10};
        int n = arr.length;
        Query q[] = {new Query(0, 5),
                  new Query(1, 4),
                  new Query(3, 7)
        };
        int m = q.length;

        buildLookup(arr, n);
        getMinimumNumber(arr, n, q, m);
    }
}
Minimum of [0, 5] is 2
Minimum of [1, 4] is 5
Minimum of [3, 7] is 6

जटिलताको लागि विश्लेषण

समय जटिलता

O (n लग एन) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो।

ठाउँ जटिलता

O (n लग एन) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो।

संदर्भ