રેન્જ ન્યૂનતમ ક્વેરી (સ્ક્વેર રુટ વિઘટન અને છૂટાછવાયા કોષ્ટક)  


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન Google
અરે સેગમેન્ટ-ટ્રી

રેન્જ લઘુત્તમ ક્વેરી સમસ્યામાં અમે ક્વેરી અને પૂર્ણાંક આપ્યો છે એરે. દરેક ક્વેરીમાં દરેક શ્રેણી માટે ડાબી અને જમણી અનુક્રમણિકાઓ તરીકેની શ્રેણી શામેલ હોય છે. આપેલ કાર્ય એ શ્રેણીમાં રહેલી બધી સંખ્યાની ન્યૂનતમ નક્કી કરવાનું છે.

ઉદાહરણ  

ઇનપુટ:

એરે [] = {2, 5, 8, 6, 13, 9, 7, 10}

ક્વેરી = {(0, 5), (1, 4), (3, 7)}

આઉટપુટ:

2 5 6

સમજૂતી:

The 2, 2, 5, 8, 6, 13 range શ્રેણી નંબરોમાં 9 એ ન્યૂનતમ છે

The 5, 5, 8, 6 range શ્રેણીની સંખ્યામાં ન્યૂનતમ 13 છે

The 6, 6, 13, 9, 7 range શ્રેણી નંબરોમાં 10 એ ન્યૂનતમ છે

રેન્જ ન્યૂનતમ ક્વેરી (સ્ક્વેર રુટ વિઘટન અને છૂટાછવાયા કોષ્ટક)પિન

અલ્ગોરિધમ  

  1. 2D એરે બનાવો અને તેને બનાવો. તેના માટે, 0 ને ચિહ્નિત કરોth તેની પંક્તિ અનુક્રમણિકા મૂલ્ય તરીકે દરેક પંક્તિની ક columnલમ.
  2. એરેને પસાર કરો, અને તપાસો કે જો i, j-1 એ લુકઅપ એરેનો એરે i + 2 પરના લુકઅપ એરે કરતા ઓછો છે કે નહીં.j-1, j-1, જો ખરું હોય તો i, j પર લુકઅપ એરે અપડેટ કરો, i, j-1 પર લુકઅપ એરે.
  3. અન્યથા i + j પર લુકઅપ એરે અપડેટ કરો, i + 2 પર લુકઅપ એરે તરીકેj-1, જે-1
  4. દરેક આપેલ ક્વેરી માટે, ક્વેરીની ડાબી અને જમણી રેન્જ મેળવો, જમણી-ડાબી +1 નું લ valueગ મૂલ્ય મેળવો અને તપાસો કે ડાબી બાજુ જો લુકઅપની એરે જમણી - 2 ની શોધની એરેની બરાબર છે.j +1, j, પછી જમણી - 2 પર લુકઅપના એરે તરીકે મૂલ્ય પરત કરોj + 1, જે.
  5. પરત કરેલ કિંમત છાપો
આ પણ જુઓ
બે સૂચિઓનો ન્યૂનતમ સૂચકાંકનો સરવાળો

રેન્જ લઘુત્તમ ક્વેરી (સ્ક્વેર રુટ વિઘટન અને છૂટાછવાયા કોષ્ટક) માટેનું વર્ણન  

અમે પૂર્ણાંક એરે અને શ્રેણી ક્વેરી આપી છે, અમે તમામ પૂર્ણાંક મૂલ્યો વચ્ચેનું ન્યુનત્તમ મૂલ્ય શોધવા અને તે મૂલ્ય પાછા આપવાનું કહ્યું છે, તેના માટે આપણે લુકઅપ એરે બનાવીશું. સોલ્યુશનમાં ફક્ત n જગ્યાના વર્ગમૂળની જરુર પડે છે પરંતુ sqrt (n) સમયનો વપરાશ થશે, જ્યારે દરેક આપેલ ક્વેરી માટે, તે સતત સમય લેશે પરંતુ એક વધારાનું સ્થાન લેશે. અમે આમાં જે વિચાર રજૂ કરીશું તે એ છે કે કદ 2 ની સબરામાંના તમામ સંભવિત લઘુત્તમ મૂલ્યો નક્કી કરવાj જ્યાં જે એન લ logગ પર જઈ શકે છે.

આપણે લુકઅપ ટેબલ બનાવીશું, તેના માટે આપણે લુકઅપ એરેનો ઉપયોગ કરીશું. લૂપ અપ એરેના બિલ્ડિંગમાં, i પર દરેક લુકઅપ માટે, j એ i થી 2 ની ન્યૂનતમ રેન્જ ધરાવે છે.J. I, j પર લુકઅપ એરે એરેના દરેક મૂલ્ય પર મૂલ્યોના અનુક્રમણિકાને પકડી રાખશે. એરેમાંથી પસાર થતાં, અમે પાવર જે પર ઉભા કરેલા 2 જેટલા શક્ય કદની કોઈપણ શ્રેણી માટે ન્યૂનતમ મૂલ્ય નક્કી કરીશું. આને લીધે, અમે આપેલ રેન્જ પર સંભવિત મૂલ્ય શોધી શકશું.

કોઈપણ આપેલ રેન્જ ક્વેરી માટે, આપણે 2 ની શક્તિની જેમ રેન્જનો ઉપયોગ કરીશું, આપણે જમણી-ડાબી + 1 ના તફાવતનો લ logગ શોધવા માટે રેંજ વેલ્યુનો ઉપયોગ કરીશું, તો પછી આપણે ડાબી બાજુ લુકઅપની એરેની તુલના કરીશું, j જમણી એરે કરતા નાના છે - 2j + 1, j, જો સ્થિતિ સાચી લાગે છે, તો પછી ડાબી બાજુ લુકઅપ પર એરેની કિંમત પરત કરો, j, નહિંતર લુકઅપ પર એરેને જમણી બાજુ પરત કરો - 2j + 1, જે. આ જરૂરી જવાબ હશે.

આ પણ જુઓ
એરેનો ઉપયોગ કર્યા વિના બીએસટીને મીન-apગલામાં કન્વર્ટ કરો

અમલીકરણ  

સીમા + ન્યૂનતમ ક્વેરી (સ્ક્વેર રુટ વિઘટન અને સ્પેર્સ કોષ્ટક) માટે સી ++ પ્રોગ્રામ

#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

માટે જટિલતા વિશ્લેષણ  

સમય જટિલતા

ઓ (એન લ nગ એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

આ પણ જુઓ
સ triર્ટ થયેલ એરેમાં તમામ ટ્રિપ્લેટ્સ છાપો જે એપી બનાવે છે

અવકાશ જટિલતા

ઓ (એન લ nગ એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

સંદર્ભ