Обхват Минимална заявка (Разлагане на квадратен корен и оскъдна таблица)  


Ниво на трудност Трудно
Често задавани в Амазонка ябълка Google
Array Сегментно дърво

В проблема с минималната заявка за обхвата сме дали заявка и цяло число масив. Всяка заявка съдържа диапазона като ляв и десен индекс за всеки диапазон. Дадената задача е да се определи минимумът от цялото число, което се намира в диапазона.

Пример  

Вход:

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}

5 е минимумът от числата на диапазона {5, 8, 6, 13}

6 е минимумът от числата на диапазона {6, 13, 9, 7, 10}

Обхват Минимална заявка (Разлагане на квадратен корен и оскъдна таблица)щифт

алгоритъм  

  1. Създайте 2D масив и го изградете. За това маркирайте 0th колона на всеки ред като стойност на индекса на реда.
  2. Прекосете масива и проверете дали масивът на търсещия масив в i, j-1 е по-малък от масива на търсещия масив при i + 2к-1, j-1, ако е вярно, актуализирайте справочния масив при i, j като справочен масив при i, j-1.
  3. В противен случай актуализирайте търсещия масив при i, j като справочен масив при i + 2к-1, j-1
  4. За всяка дадена заявка вземете левия и десния диапазон на заявката, вземете регистрационната стойност на дясно-ляво + 1 и проверете дали масивът за търсене вляво, j е по-малък от равен на масива за търсене вдясно - 2j +1, j, след това върнете стойността като масив за търсене вдясно - 2j + 1, j.
  5. Отпечатайте върнатата стойност
Вижте също
Минимална индексна сума от два списъка

Обяснение за минимална заявка за обхват (Разлагане на квадратен корен и оскъдна таблица)  

Дадохме целочислен масив и заявка за диапазон, поискахме да открием минималната стойност сред всички целочислени стойности и да върнем тази стойност, за това ще изградим търсещия масив. Решението изисква само квадратния корен от n пространство, но ще отнеме sqrt (n) време, докато за всяка дадена заявка ще отнеме постоянното време, но допълнително пространство. Идеята, която ще изложим в това, е да определим всички възможни минимални стойности в подмасив с размер 2j където j може да се изкачи до log на n.

Ще изграждаме справочна таблица, за това ще използваме справочен масив. В изграждането на цикъл нагоре по масива, за всяко търсене в i, j задържа минимум от стойностите в диапазона от i до 2J. Търсещият масив в i, j ще съдържа индексите на стойностите при всяка стойност на масива. Докато обхождаме масива, ще определим минималната стойност за всеки даден диапазон от възможен размер като 2, повишена до степен j. Поради това ще можем да разберем възможната стойност при дадените диапазони.

За всяка дадена заявка за диапазон ще използваме диапазони, както е в степента на 2. Ще използваме стойностите на диапазона, за да намерим дневника на разликата от дясно-ляво + 1. След това ще сравним масива от търсене вляво, j е по-малък от масива отдясно - 2j + 1, j, ако се установи, че условието е вярно, върнете стойността на масива при търсене вляво, j, иначе върнете масива при търсене вдясно - 2j + 1, j. Това ще бъде задължителният отговор.

Вижте също
Преобразувайте BST в Min-Heap, без да използвате масив

изпълнение  

Програма 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

Java програма за минимална заявка за обхват (Разлагане на квадратния корен и оскъдна таблица)

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 Log n) където "н" е броят на елементите в масива.

Вижте също
Отпечатайте всички триплети в сортиран масив, които образуват AP

Сложност на пространството

O (n Log n) където "н" е броят на елементите в масива.

препратка