வரம்பு குறைந்தபட்ச வினவல் (சதுர வேர் சிதைவு மற்றும் சிதறிய அட்டவணை)


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது அமேசான் ஆப்பிள் கூகிள்
அணி பிரிவு-மரம்

வரம்பின் குறைந்தபட்ச வினவல் சிக்கலில் நாங்கள் ஒரு வினவலையும் ஒரு முழு எண்ணையும் கொடுத்துள்ளோம் வரிசை. ஒவ்வொரு வினவலும் ஒவ்வொரு வரம்பிற்கும் இடது மற்றும் வலது குறியீடுகளாக வரம்பைக் கொண்டுள்ளது. கொடுக்கப்பட்ட பணி வரம்பிற்குள் இருக்கும் அனைத்து எண்ணின் குறைந்தபட்சத்தையும் தீர்மானிப்பதாகும்.

உதாரணமாக

உள்ளீடு:

arr [] = {2, 5, 8, 6, 13, 9, 7, 10}

வினவல் = {(0, 5), (1, 4), (3, 7)}

வெளியீடு:

2 5 6

விளக்கம்:

2 2, 5, 8, 6, 13, 9 range வரம்பு எண்களில் குறைந்தபட்சம் XNUMX

5, 5, 8, 6 range வரம்பு எண்களில் 13 மிகக் குறைவு

6 6, 13, 9, 7, 10 range வரம்பு எண்களில் குறைந்தபட்சம் XNUMX

வரம்பு குறைந்தபட்ச வினவல் (சதுர வேர் சிதைவு மற்றும் சிதறிய அட்டவணை)

அல்காரிதம்

  1. 2 டி வரிசையை உருவாக்கி அதை உருவாக்குங்கள். அதற்கு, 0 ஐக் குறிக்கவும்th ஒவ்வொரு வரிசையின் நெடுவரிசையும் அதன் வரிசை குறியீட்டு மதிப்பாக.
  2. வரிசையைத் தாண்டி, i, j-1 இல் உள்ள பார்வை வரிசையின் வரிசை i + 2 இல் உள்ள தேடல் வரிசையின் வரிசையை விட குறைவாக இருக்கிறதா என்று சோதிக்கவும்.J-1, j-1, உண்மையாக இருந்தால், i, j இல் தேடல் வரிசையை i, j-1 இல் தேடல் வரிசையாக புதுப்பிக்கவும்.
  3. I + 2 இல் தேடல் வரிசையாக i, j இல் தேடல் வரிசையை புதுப்பிக்கவும்J-1, ஜே -1
  4. கொடுக்கப்பட்ட ஒவ்வொரு வினவலுக்கும், வினவலின் இடது மற்றும் வலது வரம்பைப் பெறுங்கள், வலது-இடது + 1 இன் பதிவு மதிப்பைப் பெற்று, இடதுபுறத்தில் தேடலின் வரிசை இருந்தால் சரிபார்க்கவும், j வலதுபுறத்தில் பார்க்கும் வரிசைக்கு சமமானதா - 2j +1, j, பின்னர் மதிப்பை வலதுபுறம் பார்க்கும் வரிசையாகத் திருப்புக - 2j + 1, ஜெ.
  5. திரும்பிய மதிப்பை அச்சிடுக

வரம்பு குறைந்தபட்ச வினவலுக்கான விளக்கம் (சதுர வேர் சிதைவு மற்றும் சிதறிய அட்டவணை)

நாங்கள் ஒரு முழு எண் வரிசை மற்றும் வரம்பு வினவலைக் கொடுத்துள்ளோம், எல்லா முழு மதிப்புகளிலும் குறைந்தபட்ச மதிப்பைக் கண்டுபிடித்து அந்த மதிப்பைத் தருமாறு கேட்டுள்ளோம், அதற்காக நாங்கள் தேடல் வரிசையை உருவாக்குவோம். தீர்வுக்கு n இடத்தின் சதுர வேர் மட்டுமே தேவைப்படுகிறது, ஆனால் சதுரடி (n) நேரத்தை எடுத்துக்கொள்ளும், அதேசமயம் கொடுக்கப்பட்ட ஒவ்வொரு வினவலுக்கும் நிலையான நேரம் எடுக்கும், ஆனால் கூடுதல் இடம் தேவைப்படும். இதில் நாம் முன்வைக்கும் யோசனை, அளவு 2 இன் துணை வரிசையில் சாத்தியமான அனைத்து குறைந்தபட்ச மதிப்புகளையும் தீர்மானிப்பதாகும்j j இன் பதிவு வரை செல்லலாம்.

நாங்கள் ஒரு தேடல் அட்டவணையை உருவாக்குவோம், அதற்காக நாங்கள் ஒரு தேடல் வரிசையைப் பயன்படுத்துவோம். வரிசையை வளையத்தை உருவாக்குவதில், i இல் ஒவ்வொரு பார்வைக்கும், j குறைந்தபட்சம் i முதல் 2 வரையிலான மதிப்புகளை வைத்திருக்கும்J. I, j இல் உள்ள தேடல் வரிசை, வரிசையின் ஒவ்வொரு மதிப்பிலும் மதிப்புகளின் குறியீடுகளை வைத்திருக்கும். வரிசை வழியாக பயணிக்கும்போது, ​​எந்தவொரு சாத்தியமான வரம்பிற்கும் குறைந்தபட்ச மதிப்பை 2 சக்தியாக உயர்த்துவோம். இதன் காரணமாக, கொடுக்கப்பட்ட வரம்புகளில் சாத்தியமான மதிப்பைக் கண்டுபிடிக்க முடியும்.

எந்தவொரு வரம்பு வினவலுக்கும், 2 இன் சக்திகளைப் போலவே வரம்புகளையும் பயன்படுத்துவோம். வலது-இடது + 1 இன் வேறுபாட்டின் பதிவைக் கண்டுபிடிக்க வரம்பு மதிப்புகளைப் பயன்படுத்துவோம். பின்னர் இடதுபுறத்தில் தேடும் வரிசையை ஒப்பிடுவோம், j வலது வரிசையை விட சிறியது - 2j + 1, j, நிபந்தனை உண்மை எனக் கண்டறியப்பட்டால், வரிசையின் மதிப்பை இடதுபுறத்தில் தேடுங்கள், j, இல்லையெனில் வலதுபுறத்தில் வரிசையைத் திரும்பவும் - 2j + 1, ஜெ. இது தேவையான பதிலாக இருக்கும்.

நடைமுறைப்படுத்தல்

வரம்பு குறைந்தபட்ச வினவலுக்கான சி ++ நிரல் (சதுர வேர் சிதைவு மற்றும் சிதறிய அட்டவணை)

#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) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.

விண்வெளி சிக்கலானது

O (n பதிவு n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.

குறிப்பு