trouver la différence maximale entre j et i indices tels que j> i et a [j]> a [i] dans O (n)

Question

Étant donné un tableau non-trié, trouver l' max j - i de la différence entre les indices tels que j > i et a[j] > a[i] en O(n). Je suis en mesure de trouver j et i à l'aide de méthodes triviales en O(n^2) de complexité, mais voudrais savoir comment le faire, en O(n)?

Entrée: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}

Sortie: 8 ( j = 8, i = 0)

Entrée: {1, 2, 3, 4, 5, 6}

Sortie: 5 (j = 5, i = 0)

Answer 1

Par souci de concision, je vais supposer que tous les éléments sont uniques. L'algorithme peut être étendu pour gérer les non-unique élément de cas.

Tout d'abord, observons que si x et y sont de votre choix, max et min endroits, respectivement, alors il ne peut pas être a[i] > a[x] et i > x, et de la même façon, a[j] < a[y] et j < y.

Donc, nous balayage le long de la matrice a et de construire un tableau S tels que S[i] porte l'index de l'élément minimum en a[0:i]. De même, un tableau T qui détient l'indice de l'élément maximum en a[n-1:i] (c'est à dire, à l'envers).

Maintenant, nous pouvons voir qu' a[S[i]] et a[T[i]] sont nécessairement la diminution de séquences, depuis qu'ils ont été au minimum jusqu' i et maximum de n jusqu'à i respectivement.

Alors maintenant, nous essayons de faire une fusion de tri comme procédure. À chaque étape, si a[S[head]] < a[T[head]], nous détacher un élément d' T, sinon nous détacher un élément d' S. À chaque étape, nous enregistrons la différence dans la tête de la S et T s' a[S[head]] < a[T[head]]. Le maximum d'une telle différence vous donne votre réponse.

EDIT: Voici un code simple en Python la mise en œuvre de l'algorithme.

def getMaxDist(arr):

    # get minima going forward
    minimum = float("inf")
    minima = collections.deque()
    for i in range(len(arr)):
        if arr[i] < minimum:
            minimum = arr[i]
            minima.append((arr[i], i))

    # get maxima going back
    maximum = float("-inf")
    maxima = collections.deque()
    for i in range(len(arr)-1,0,-1):
        if arr[i] > maximum:
            maximum = arr[i]
            maxima.appendleft((arr[i], i))

    # do merge between maxima and minima
    maxdist = 0
    while len(maxima) and len(minima):
        if maxima[0][0] > minima[0][0]:
            if maxima[0][1] - minima[0][1] > maxdist:
                maxdist = maxima[0][1] - minima[0][1]
            maxima.popleft()
        else:
            minima.popleft()

    return maxdist

Answer 2

Nous allons faire de cette simple observation: Si nous avons 2 éléments a[i], a[j] avec i < j et a[i] < a[j], alors nous pouvons être sûrs que j de ne pas être partie de la solution que le premier élément (il peut être la seconde, mais c'est une deuxième histoire) parce que je voudrais être une meilleure alternative.

Ce que cela nous dit, c'est que, si nous construisons goulûment une diminution de la séquence à partir des éléments de la partie gauche de la réponse va sûrement venir de là.

Par exemple pour : 12 3 61 23 51 2 le goulûment diminuer la séquence est construite comme ceci:

12 -> 12 3 -> nous ignorer 61 parce que c'est pire que le 3 -> nous ignorer 23 parce que c'est pire que le 3 -> nous ignorer 51 parce que c'est pire que le 3 -> 12 3 2.

Donc la réponse devrait contenir, sur le côté gauche 12 3 ou 2.

Maintenant sur un cas aléatoire cela a O(log N) la longueur de sorte que vous pouvez recherche binaire pour chaque élément dans la partie droite de la réponse et vous auriez O(N log log N) ce qui est bon, et si vous appliquez la même logique sur la partie droite de la chaîne de caractères aléatoire cas, vous pouvez obtenir O(log^2 N + N(de la lecture)) qui est O(N). Mais nous pouvons faire en O(N) sur une base non aléatoire en cas de trop.

Supposons que nous avons cette diminution de la séquence. Nous commençons à partir de la droite de la chaîne et de faire ce qui suit si l'on peut coupler le dernier de la diminution de la séquence avec le nombre actuel

1) Si nous avons trouvé une meilleure solution en prenant le dernier de la diminution de la séquence et le nombre actuel que nous mettons à jour la réponse

2) Même si nous avons mis à jour la réponse ou pas, nous pop le dernier élément de la diminution de la séquence parce que nous sommes c'est match parfait (n'importe quel autre match serait pour la gauche et donnerait une réponse avec les petits j - i)

3) Répétez alors que nous pouvons paire de ces 2

Exemple De Code:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N; cin >> N;

    vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i)
        cin >> A[i];

    // let's solve the problem
    vector<int> decreasing; 

    pair<int, int> answer;

    // build the decreasing sequence
    decreasing.push_back(1);
    for (int i = 1; i <= N; ++i)
        if (A[i] < A[decreasing.back()])
            decreasing.push_back(i); // we work with indexes because we might have equal values

    for (int i = N; i > 0; --i) {
        while (decreasing.size() and A[decreasing.back()] < A[i]) { // while we can pair these 2
            pair<int, int> current_pair(decreasing.back(), i);
            if (current_pair.second - current_pair.first > answer.second - answer.first)
                answer = current_pair;
            decreasing.pop_back();
        }
    }

    cout << "Best pair found: (" << answer.first << ", " << answer.second << ") with values (" << A[answer.first] << ", " << A[answer.second] << ")\n";
}

Plus Tard Edit: Je vois que vous avez donné un exemple: j'ai indexé de 1 à rendre plus clair et j'ai l'impression (i, j) au lieu de (j, i). Vous pouvez le modifier comme bon vous semble.

Answer 3

Méthode 1 (Simple mais Inefficace)

Exécuter deux boucles. Dans la boucle externe, choisir les éléments un par un à partir de la gauche. Dans l'intérieur de la boucle, de comparer l'élément choisi avec les éléments à partir du côté droit. Arrêt de la boucle interne lorsque vous voyez un élément plus grand que l'élément choisi et de continuer à mettre à jour le maximum de j-je si loin.

#include <stdio.h>
/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff = -1;
    int i, j;

    for (i = 0; i < n; ++i)
    {
        for (j = n-1; j > i; --j)
        {
            if(arr[j] > arr[i] && maxDiff < (j - i))
                maxDiff = j - i;
        }
    }

    return maxDiff;
}

int main()
{
    int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxDiff = maxIndexDiff(arr, n);
    printf("\n %d", maxDiff);
    getchar();
    return 0;
}

Le temps de la Complexité: O(n^2)

---

Méthode 2 (Efficace)

Pour résoudre ce problème, nous devons obtenir deux optimale des indices d'arr[]: index gauche je et droit de l'indice j. Pour un élément arr[i], nous n'avons pas besoin de considérer arr[i] pour l'index gauche si il y a un élément plus petit que arr[i] sur le côté gauche de l'arr[i].
De même, si il y a un plus grand élément sur le côté droit de l'arr[j], alors nous n'avons pas besoin d'examiner cette j pour l'index droit. Nous avons donc la construction de deux auxiliaires de tableaux LMin[] et RMax[] telle que LMin[i] détient le plus petit élément sur le côté gauche de l'arr[i], y compris arr[i], et RMax[j] détient le plus grand élément sur le côté droit de l'arr[j], y compris arr[j].
Après la construction de ces deux auxiliaires des tableaux, nous avons traverse ces deux tableaux à partir de la gauche vers la droite. En traversant LMin[] et RMa[] si nous voyons que LMin[i] est plus grand que RMax[j], alors nous devons aller de l'avant dans LMin[] (ou ne i++) parce que tous les éléments à gauche de LMin[i] est supérieur ou égal à LMin[i]. Sinon, nous devons aller de l'avant dans RMax[j] pour obtenir un plus grand j – j'ai de la valeur.

#include <stdio.h>

/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
    return x > y? x : y;
}

int min(int x, int y)
{
    return x < y? x : y;
}

/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;

    int *LMin = (int *)malloc(sizeof(int)*n);
    int *RMax = (int *)malloc(sizeof(int)*n);

   /* Construct LMin[] such that LMin[i] stores the minimum value
       from (arr[0], arr[1], ... arr[i]) */
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = min(arr[i], LMin[i-1]);

    /* Construct RMax[] such that RMax[j] stores the maximum value
       from (arr[j], arr[j+1], ..arr[n-1]) */
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = max(arr[j], RMax[j+1]);

    /* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }

    return maxDiff;
}

/* Driver program to test above functions */
int main()
{
    int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxDiff = maxIndexDiff(arr, n);
    printf("\n %d", maxDiff);
    getchar();
    return 0;
}

Le temps de la Complexité: O(n)
Auxiliaire de l'Espace: O(n)
Source geeksforgeeks

Answer 4

Pour résoudre ce problème, nous devons obtenir deux optimale des indices d'arr[]: index gauche je et droit de l'indice j. Pour un élément arr[i], nous n'avons pas besoin de considérer arr[i] pour l'index gauche si il y a un élément plus petit que arr[i] sur le côté gauche de l'arr[i]. De même, si il y a un plus grand élément sur le côté droit de l'arr[j], alors nous n'avons pas besoin d'examiner cette j pour l'index droit. Nous avons donc la construction de deux auxiliaires de tableaux LMin[] et RMax[] telle que LMin[i] détient le plus petit élément sur le côté gauche de l'arr[i], y compris arr[i], et RMax[j] détient le plus grand élément sur le côté droit de l'arr[j], y compris arr[j]. Après la construction de ces deux auxiliaires des tableaux, nous avons traverse ces deux tableaux à partir de la gauche vers la droite. En traversant LMin[] et RMa[] si nous voyons que LMin[i] est plus grand que RMax[j], alors nous devons aller de l'avant dans LMin[] (ou ne i++) parce que tous les éléments à gauche de LMin[i] est supérieur ou égal à LMin[i]. Sinon, nous devons aller de l'avant dans RMax[j] pour obtenir un plus grand j – j'ai de la valeur. Voici le code c exécute en O(n) temps:

#include <stdio.h>
#include <stdlib.h>

/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
    return x > y? x : y;
}

int min(int x, int y)
{
    return x < y? x : y;
}

/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;

    int *LMin = (int *)malloc(sizeof(int)*n);
    int *RMax = (int *)malloc(sizeof(int)*n);

   /* Construct LMin[] such that LMin[i] stores the minimum value
       from (arr[0], arr[1], ... arr[i]) */
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = min(arr[i], LMin[i-1]);

    /* Construct RMax[] such that RMax[j] stores the maximum value
       from (arr[j], arr[j+1], ..arr[n-1]) */
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = max(arr[j], RMax[j+1]);

    /* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }

    return maxDiff;
}

/* Driver program to test above functions */
int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxDiff = maxIndexDiff(arr, n);
    printf("\n %d", maxDiff);
    getchar();
    return 0;
}

Answer 5

Je pense amélioration par rapport à O(n^2), mais il faut vérifier si cela est O(n) dans le pire des cas ou pas.

• Créer une variable BestSoln=0; et de parcourir le tableau pour le premier élément et de stocker la meilleure solution pour le premier élément que j'ai.e bestSoln=k;.
• Maintenant pour la 2e élément de considérer uniquement les éléments qui sont k distances à partir du deuxième élément.
• Si BestSoln dans ce cas c'est mieux que la première itération, puis remplacer c'est le contraire la laisser comme ça. Garder l'itération pour les autres éléments.

Il peut encore être amélioré si nous conservons max élément pour chaque subarray à partir de i à la fin. Cela peut être fait en O(n) en parcourant le tableau de la fin. Si un élément particulier est plus que c'est local max puis il n'y a pas besoin de faire de l'évaluation de cet élément.

Entrée:

{9, 2, 3, 4, 5, 6, 7, 8, 18, 0}

créer des local max tableau pour ce tableau:

[18,18,18,18,18,18,18,0,0] O(n).

Maintenant, parcourir le tableau pour 9 ,ici, la meilleure solution sera i=0,j=8. Maintenant, pour le deuxième élément, ou après, nous n'avons pas besoin d'évaluer. et la meilleure solution est - i=0,j=8.

Mais supposons que la matrice est d'Entrée:

{19, 2, 3, 4, 5, 6, 7, 8, 18, 0,4}

Local max array [18,18,18,18,18,18,18,0,0] puis dans la première itération nous n'avons pas besoin d'évaluer locales max est moins courant elem.

Maintenant, pour la deuxième itération meilleure solution est, i=1,j=10. Maintenant pour les autres éléments que nous n'avez pas besoin de considérer l'évaluation comme ils ne peuvent pas donner la meilleure solution.

Laissez-moi savoir votre point de vue à votre cas d'utilisation à laquelle ma solution n'est pas applicable.