ശ്രേണി മിനിമം അന്വേഷണം (സ്ക്വയർ റൂട്ട് വിഘടനവും വിരള പട്ടികയും)


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ ഗൂഗിൾ
അറേ സെഗ്മെന്റ്-ട്രീ

ശ്രേണിയിലെ ഏറ്റവും കുറഞ്ഞ ചോദ്യ പ്രശ്‌നത്തിൽ‌ ഞങ്ങൾ‌ ഒരു ചോദ്യവും ഒരു സംഖ്യയും നൽകി ശ്രേണി. ഓരോ അന്വേഷണത്തിനും ഓരോ ശ്രേണിയുടെയും ഇടത്, വലത് സൂചികകളായി ശ്രേണി അടങ്ങിയിരിക്കുന്നു. പരിധിക്കുള്ളിലുള്ള എല്ലാ സംഖ്യകളുടെയും ഏറ്റവും കുറഞ്ഞ എണ്ണം നിർണ്ണയിക്കുക എന്നതാണ് തന്നിരിക്കുന്ന ചുമതല.

ഉദാഹരണം

ഇൻപുട്ട്:

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

ചോദ്യം = {(0, 5), (1, 4), (3, 7)}

ഔട്ട്പുട്ട്:

2 5 6

വിശദീകരണം:

2, 2, 5, 8, 6, 13 the ശ്രേണി നമ്പറുകളിൽ ഏറ്റവും കുറഞ്ഞത് 9 ആണ്

Range 5, 5, 8, 6 the ശ്രേണി നമ്പറുകളിൽ ഏറ്റവും കുറഞ്ഞത് 13 ആണ്

6 6, 13, 9, 7, 10 the ശ്രേണി നമ്പറുകളിൽ ഏറ്റവും കുറഞ്ഞത് XNUMX ആണ്

ശ്രേണി മിനിമം അന്വേഷണം (സ്ക്വയർ റൂട്ട് വിഘടനവും വിരള പട്ടികയും)

അൽഗോരിതം

  1. ഒരു 2 ഡി അറേ സൃഷ്ടിച്ച് അത് നിർമ്മിക്കുക. അതിനായി 0 എന്ന് അടയാളപ്പെടുത്തുകth ഓരോ വരിയുടെയും നിരയുടെ വരി സൂചിക മൂല്യമായി.
  2. അറേയിലൂടെ സഞ്ചരിച്ച്, i, 1 ലെ ലുക്ക്അപ്പ് അറേയുടെ ശ്രേണി i + 2 ലെ ലുക്ക്അപ്പ് അറേയുടെ അറേയേക്കാൾ കുറവാണോയെന്ന് പരിശോധിക്കുക.j-1, j-1, ശരിയാണെങ്കിൽ, i, j-1 ലെ ലുക്ക്അപ്പ് അറേ ആയി ലുക്ക്അപ്പ് അറേ അപ്ഡേറ്റ് ചെയ്യുക.
  3. I, 2 ലെ ലുക്ക്അപ്പ് അറേ അപ്‌ഡേറ്റ് ചെയ്യുകj-1, ജെ -1
  4. തന്നിരിക്കുന്ന ഓരോ ചോദ്യത്തിനും, ചോദ്യത്തിന്റെ ഇടത്, വലത് ശ്രേണി നേടുക, വലത്-ഇടത് + 1 ന്റെ ലോഗ് മൂല്യം നേടുക, ഇടതുവശത്തുള്ള ലുക്ക്അപ്പിന്റെ നിരയാണോയെന്ന് പരിശോധിക്കുക, j വലതുവശത്തുള്ള ലുക്കപ്പിന്റെ അറേയ്‌ക്ക് തുല്യമാണോയെന്ന് പരിശോധിക്കുക - 2j +1, j, തുടർന്ന് വലതുവശത്തുള്ള ലുക്കപ്പിന്റെ ഒരു നിരയായി മൂല്യം നൽകുക - 2j + 1, ജെ.
  5. നൽകിയ മൂല്യം അച്ചടിക്കുക

ശ്രേണി മിനിമം അന്വേഷണത്തിനുള്ള വിശദീകരണം (സ്ക്വയർ റൂട്ട് വിഘടനവും വിരള പട്ടികയും)

ഞങ്ങൾ‌ ഒരു ഇൻ‌റിജർ‌ അറേയും ഒരു ശ്രേണി അന്വേഷണവും നൽകി, എല്ലാ ഇൻ‌റിജർ‌ മൂല്യങ്ങളിൽ‌ ഏറ്റവും കുറഞ്ഞ മൂല്യം കണ്ടെത്താനും ആ മൂല്യം തിരികെ നൽകാനും ഞങ്ങൾ‌ ആവശ്യപ്പെട്ടു, അതിനായി ഞങ്ങൾ‌ ലുക്ക്അപ്പ് അറേ നിർമ്മിക്കും. പരിഹാരത്തിന് n സ്‌പെയ്‌സിന്റെ സ്‌ക്വയർ റൂട്ട് മാത്രമേ ആവശ്യമുള്ളൂ, പക്ഷേ അത് ചതുരശ്ര (n) സമയം ചെലവഴിക്കും, അതേസമയം നൽകിയിരിക്കുന്ന ഓരോ ചോദ്യത്തിനും സ്ഥിരമായ സമയമെടുക്കും എന്നാൽ അധിക ഇടം ആവശ്യമാണ്. വലുപ്പം 2 ന്റെ ഉപഅറേയിൽ സാധ്യമായ എല്ലാ മിനിമം മൂല്യങ്ങളും നിർണ്ണയിക്കുക എന്നതാണ് ഞങ്ങൾ ഇതിൽ മുന്നോട്ട് വയ്ക്കുന്നത്j ഇവിടെ j ന് n ന്റെ ലോഗിലേക്ക് പോകാം.

ഞങ്ങൾ ഒരു ലുക്ക്അപ്പ് പട്ടിക നിർമ്മിക്കും, അതിനായി ഞങ്ങൾ ഒരു ലുക്ക്അപ്പ് അറേ ഉപയോഗിക്കും. ലൂപ്പ് അപ്പ് അറേയുടെ നിർമ്മാണത്തിൽ, i- ലെ ഓരോ ലുക്കപ്പിനും j, i മുതൽ 2 വരെയുള്ള മൂല്യങ്ങളുടെ ഏറ്റവും ചുരുങ്ങിയത് പിടിക്കുകJ. I, j ലെ ലുക്ക്അപ്പ് അറേ, അറേയുടെ ഓരോ മൂല്യത്തിലും മൂല്യങ്ങളുടെ സൂചികകൾ പിടിക്കും. അറേയിലൂടെ സഞ്ചരിക്കുമ്പോൾ, പവർ 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” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.

അവലംബം