Ελάχιστο ερώτημα εύρους (αποσύνθεση τετραγωνικής ρίζας και αραιός πίνακας)


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις αμαζόνα μήλο Google
Παράταξη Τμήμα-δέντρο

Στο πρόβλημα ελάχιστου ερωτήματος εύρους έχουμε δώσει ένα ερώτημα και έναν ακέραιο παράταξη. Κάθε ερώτημα περιέχει το εύρος ως αριστερά και δεξιά ευρετήρια για κάθε εύρος. Η δεδομένη εργασία είναι να προσδιοριστεί ο ελάχιστος όλος αριθμός που βρίσκεται εντός του εύρους.

Παράδειγμα

εισόδου:

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 + 2j-1, j-1, εάν ισχύει τότε ενημερώστε τον πίνακα αναζήτησης στο i, j ως πίνακας αναζήτησης στο i, j-1.
  3. Διαφορετικά, ενημερώστε τον πίνακα αναζήτησης στο i, j ως πίνακας αναζήτησης στο i + 2j-1, j-1
  4. Για κάθε δεδομένο ερώτημα, λάβετε το αριστερό και το δεξί εύρος του ερωτήματος, λάβετε την τιμή καταγραφής του δεξιού-αριστερού + 1 και ελέγξτε αν ο πίνακας αναζήτησης στα αριστερά, j είναι μικρότερος από το ίδιο με τον πίνακα αναζήτησης στα δεξιά - 2j +1, j και, στη συνέχεια, επιστρέψτε την τιμή ως πίνακας αναζήτησης στα δεξιά - 2j + 1, j.
  5. Εκτυπώστε την επιστρεφόμενη τιμή

Επεξήγηση για το ελάχιστο ερώτημα εύρους (αποσύνθεση τετραγωνικής ρίζας και αραιός πίνακας)

Έχουμε δώσει έναν ακέραιο πίνακα και ένα ερώτημα εύρους, ζητήσαμε να μάθουμε την ελάχιστη τιμή μεταξύ όλων των ακέραιων τιμών και να επιστρέψουμε αυτήν την τιμή, για αυτό θα δημιουργήσουμε τον πίνακα αναζήτησης. Η λύση απαιτεί μόνο την τετραγωνική ρίζα του n space αλλά θα καταναλώνει sqrt (n) χρόνο, ενώ για κάθε δεδομένο ερώτημα, θα χρειαστεί ο σταθερός χρόνος αλλά ένας επιπλέον χώρος. Η ιδέα που θα προτείνουμε σε αυτό είναι να προσδιορίσουμε όλες τις πιθανές ελάχιστες τιμές σε μια υποπεριοχή μεγέθους 2j όπου j μπορεί να ανέβει στο log του n.

Θα φτιάχνουμε έναν πίνακα αναζήτησης, για αυτό θα χρησιμοποιούμε έναν πίνακα αναζήτησης. Στην κατασκευή του loop up του πίνακα, για κάθε αναζήτηση στο i, j κρατήστε τουλάχιστον τις τιμές που κυμαίνονται από i έως 2J. Ο πίνακας αναζήτησης στο i, j θα διατηρεί τους δείκτες των τιμών σε κάθε τιμή του πίνακα. Ενώ διασχίζουμε τη συστοιχία, θα καθορίσουμε την ελάχιστη τιμή για κάθε δεδομένο εύρος πιθανών μεγεθών ως 2 ανυψωμένα στην ισχύ j. Λόγω αυτού, θα είμαστε σε θέση να ανακαλύψουμε την πιθανή τιμή στις δεδομένες περιοχές.

Για κάθε δεδομένο ερώτημα εύρους, θα χρησιμοποιούμε εύρη όπως στις δυνάμεις του 2. Θα χρησιμοποιούμε τις τιμές εύρους για να βρούμε το αρχείο καταγραφής της διαφοράς δεξιά-αριστερά + 1. Στη συνέχεια, θα συγκρίνουμε τον πίνακα αναζήτησης στα αριστερά, j είναι μικρότερη από τη σειρά των δεξιών - 2j + 1, j, εάν διαπιστωθεί ότι η συνθήκη είναι αληθής, επιστρέψτε την τιμή του πίνακα κατά την αναζήτηση στα αριστερά, j, αλλιώς επιστρέψτε τον πίνακα κατά την αναζήτηση στα δεξιά - 2j + 1, 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

Πρόγραμμα 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) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Διαστημική πολυπλοκότητα

O (n Log n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Αναφορά