Leaders in an Array

+10

Tu reçois un tableau d’entiers nums. Un élément est un leader lorsqu’il est supérieur ou égal à tous les éléments situés à sa droite. Le dernier élément n’a aucun élément à sa droite, il est donc toujours un leader. Renvoie tous les leaders, dans l’ordre où ils apparaissent dans nums, de gauche à droite.

Fonction

leaders(nums: integer-array) → integer-array

numsinteger-array: le tableau d’entiers dans lequel effectuer la recherche
Renvoieinteger-array: les leaders de nums, de gauche à droite

Contraintes

1 ≤ nums.length ≤ 25000
-10⁹ ≤ nums[i] ≤ 10⁹

Exemples

Entrée: nums = [12, 5, 9, 3, 6, 2]
Sortie: [12, 9, 6, 2]
Explication: 2 est le dernier, donc il mène. 6 bat le 2 qui le suit, 9 bat 3, 6 et 2, et 12 bat tout le monde. 5 perd contre 9 et 3 perd contre 6, donc la réponse est [12, 9, 6, 2].

Pour aller plus loin

Si les valeurs arrivent une à une et qu’après chacune, vous devez indiquer les éléments leaders jusqu’ici, comment mettez-vous à jour la liste en temps amorti O(1) par valeur ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

En lisant de gauche à droite, chaque élément nécessite un nouveau parcours de son suffixe. Parcourez plutôt le tableau de droite à gauche : la seule chose à connaître sur le suffixe est sa valeur maximale, et une seule variable suffit à la stocker. Cela transforme une vérification en O(n²) en un seul parcours.

Vérifiez tout ce qui se trouve à droite

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Appliquez la définition : pour chaque indice i, parcourez les éléments suivants et arrêtez-vous au premier qui est strictement supérieur à nums[i]. Si le parcours atteint la fin, nums[i] est un leader. Vous testez les indices de gauche à droite, les leaders apparaissent donc dans l’ordre. Dans [12, 5, 9, 3, 6, 2], 5 s’arrête à 9 et 3 s’arrête à 6.

Le coût vient des parcours qui vont jusqu’à la fin. Avec 24 999 valeurs égales suivies d’une valeur plus grande, chaque élément parcourt presque tout le tableau : environ 25 000 × 25 000 / 2, soit plus de 3 × 10^8 comparaisons.

Algorithme

Créez une liste de résultats vide.
Pour chaque indice i, parcourez j de i + 1 jusqu’à la fin.
Si un nums[j] est supérieur à nums[i], arrêtez-vous : nums[i] n’est pas un leader.
Si aucun j de ce type n’existe, ajoutez nums[i] au résultat.
Retournez le résultat.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

Un passage depuis la droite avec un maximum courant

Intuition

Être au moins aussi grand que chaque élément situé à droite revient à être au moins aussi grand que leur maximum. En parcourant la liste de droite à gauche, tu peux maintenir ce maximum à jour. Le dernier élément est un leader et initialise le maximum. Chaque élément situé à sa gauche est un leader s’il est supérieur ou égal au maximum, puis devient le nouveau maximum ; sinon, une valeur plus grande se trouve à sa droite.

Pour [12, 5, 9, 3, 6, 2] : 2 est un leader, puis 6, puis 9, puis 12, tandis que 3 et 5 sont inférieurs au maximum. Tu as trouvé [2, 6, 9, 12] ; en inversant l’ordre, tu obtiens la réponse.

Chaque élément est comparé une fois : temps en O(n) et espace supplémentaire en O(1), en plus du résultat. La version R marque les leaders dans un vecteur logical(n), donc son espace supplémentaire est en O(n).

Algorithme

Placez le dernier élément dans le résultat et définissez best sur cet élément.
Faites décroître i du deuxième indice en partant de la fin jusqu’à 0.
Si nums[i] ≥ best, ajoutez nums[i] au résultat et définissez best sur cet élément.
Inversez le résultat pour que les leaders soient lus de gauche à droite, puis renvoyez-le.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

Pièges et cas limites

Utiliser > au lieu de ≥ par rapport au maximum courant. Dans [4, 7, 7, 1, 7], chaque 7 est un leader, mais une comparaison stricte n’en conserve que le dernier.
Initialiser le maximum à 0 au lieu de l’initialiser avec le dernier élément. [-1, -5] doit renvoyer les deux éléments, mais un maximum de 0 les exclut.
Renvoyer les leaders dans l’ordre où vous les avez trouvés, [2, 6, 9, 12] au lieu de [12, 9, 6, 2].
Ajouter deux fois le dernier élément en démarrant la boucle au dernier indice après l’avoir déjà ajouté au résultat.
Comparer chaque élément uniquement avec son voisin. Dans [5, 3, 9], 5 est supérieur au 3 qui se trouve à côté de lui, mais le 9 signifie que la réponse est [9].

Questions fréquentes3

Quelle est la complexité temporelle de la recherche des leaders dans un tableau ?

O(n) avec un seul parcours depuis la droite, car chaque élément est comparé une fois au maximum courant. Vérifier chaque élément par rapport à tout ce qui se trouve à sa droite coûte O(n²) dans le pire des cas, par exemple lorsque toutes les valeurs sont égales.

Le dernier élément est-il toujours un leader ?

Oui. Un élément est un maximum à droite s’il est au moins aussi grand que chaque élément situé à sa droite. Le dernier élément n’en a aucun, donc la condition est satisfaite sans rien avoir à vérifier.

Les valeurs égales comptent-elles comme des leaders ?

Ici, oui : un leader doit être supérieur ou égal à chaque élément situé à sa droite, donc dans [4, 7, 7, 1, 7], les trois 7 sont des leaders. Certaines versions exigent qu’il soit strictement supérieur ; dans ce cas, compare avec >, et seul le dernier des éléments égaux est un leader.

def leaders(nums):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

nums = [12, 5, 9, 3, 6, 2]

Résultat attendu

[12, 9, 6, 2]