Kth Largest Element in a Stream

Q: Pourquoi utiliser un tas min plutôt qu’un tas max pour trouver le k-ième élément le plus grand ?

La plus petite des k plus grandes valeurs est à la fois la réponse et la valeur qu’un nouvel arrivant doit dépasser, et un tas min de taille k la maintient au sommet. Un tas max contenant toutes les valeurs place la plus grande au sommet ; atteindre la k -ième valeur signifie donc en retirer k-1 et les réinsérer à chaque arrivée.

Q: Quelle est la complexité temporelle du k-ième plus grand élément dans un flux ?

Chaque arrivée coûte O(log k) : une comparaison avec le sommet et au plus un rétablissement de la propriété du tas parmi k valeurs. La construction du tas à partir de nums coûte O(n log k) , donc l’exécution complète prend un temps de O((n + m) log k) et nécessite un espace supplémentaire de O(k) .

FacileTas

+10

Un flux d’entiers commence par les valeurs de nums. Ensuite, les valeurs de adds arrivent une par une. Après chaque arrivée, enregistrez la k-ième plus grande valeur parmi toutes celles observées jusqu’à présent, en comptant séparément les valeurs égales. Renvoyez les valeurs enregistrées dans l’ordre, une pour chaque valeur de adds.

nums contient au moins k-1 valeurs, donc après la première arrivée, il y a toujours au moins k valeurs parmi lesquelles choisir.

Fonction

kthLargestStream(k: integer, nums: integer-array, adds: integer-array) → integer-array

kinteger: le rang à afficher, 1 pour la valeur la plus élevée
numsinteger-array: les valeurs déjà présentes dans le flux
addsinteger-array: les valeurs qui arrivent, dans l’ordre
Renvoieinteger-array: la k-ième valeur la plus élevée après chaque arrivée

Contraintes

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums peut être dans n’importe quel ordre, et les valeurs égales sont comptées comme des valeurs distinctes.

Exemples

Entrée: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
Sortie: [3, 5, 6, 6, 7]
Explication: Après l'arrivée de 3, le troisième plus grand nombre parmi 7, 5, 3 et 1 est 3. Ensuite, 9 le fait passer à 5, 6 le fait passer à 6, 2 ne change rien, et 8 le fait passer à 7 (9, 8, 7).

Entrée: k = 1nums = [-2]adds = [-5, 0, -1, 4]
Sortie: [-2, 0, 0, 4]
Explication: Avec k = 1, la réponse est la plus grande valeur jusqu’ici : -2 jusqu’à l’arrivée de 0, toujours 0 après -1, puis 4.

Pour aller plus loin

Comment répondrais-tu à la même question si des valeurs pouvaient également être supprimées du flux ?

Indices

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

0 sur 3 ouverts

Solution

Les valeurs ne quittent jamais le flux : une valeur qui passe sous la k-ième plus grande est donc définitivement écartée. Ne garde que les k plus grandes valeurs dans un tas min : son sommet est la réponse, et chaque nouvel élément nécessite une comparaison et au plus une mise à jour du tas en O(log k).

Trier après chaque arrivée

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Conserve chaque valeur dans une liste. Après chaque arrivée, trie la liste par ordre croissant et lis l’index length-k, qui correspond par définition au k-ième plus grand élément.

À chaque arrivée, le tri porte sur jusqu’à n + m valeurs, où n et m sont les longueurs de nums et adds. Avec 10^4 éléments de chaque côté, cela représente environ 2 × 10^9 comparaisons au total.

Algorithme

Copiez nums dans une liste values.
Pour chaque valeur de adds, ajoutez-la à values.
Triez values par ordre croissant et enregistrez values[length-k].
Renvoyez les valeurs enregistrées.

def kthLargestStream(k, nums, adds):
    values = list(nums)
    result = []
    for x in adds:
        values.append(x)
        values.sort()
        # In increasing order the k-th largest sits k places from the end.
        result.append(values[len(values) - k])
    return result

Min-tas des k plus grandes valeurs

Intuition

Dès qu’une valeur a k valeurs supérieures à elle, cela reste vrai pour le reste du flux ; seules les k plus grandes valeurs vues jusqu’à présent comptent donc. Stocke-les dans un tas min. Son sommet est la plus petite des k plus grandes valeurs, ce qui correspond exactement à la k-ième plus grande valeur au total.

Lorsque x arrive et que le tas est plein, compare-le à son sommet. Si x n’est pas plus grand, il ne fait pas partie des k plus grandes valeurs et rien ne change. S’il est plus grand, le sommet est écarté : remplace-le par x et fais descendre celui-ci dans le tas, en O(log k). Les valeurs initiales suivent la même procédure ; nums peut donc être plus long que k.

Dans le premier exemple, après nums, le tas contient 7, 1 et 5, avec 1 au sommet. La valeur 3 qui arrive remplace 1, et le sommet, 3, est la première réponse.

Algorithme

Commencez avec un tas min vide.
Pour ajouter x : si le tas contient moins de k valeurs, insérez x. Sinon, si x est plus grand que l’élément au sommet, remplacez celui-ci par x et rétablissez l’ordre du tas.
Ajoutez ainsi chaque valeur de nums.
Pour chaque valeur de adds, ajoutez-la et enregistrez l’élément au sommet du tas.
Renvoyez les valeurs enregistrées.

import heapq


def kthLargestStream(k, nums, adds):
    # A min-heap of the k largest values so far; heap[0] is the smallest of them.
    heap = []

    def add(x):
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x

    for x in nums:
        add(x)
    result = []
    for x in adds:
        add(x)
        result.append(heap[0])  # the k-th largest so far
    return result

Pièges et cas limites

Supprimer les doublons. Les quatre plus grandes valeurs parmi 9, 6, 6, 6, 2 sont 9, 6, 6 et 6. Un ensemble, ou une vérification qui ignore les valeurs déjà présentes, renvoie 2 dans le troisième exemple au lieu de 6.
Lire la réponse avant d’ajouter. Lorsque nums contient k-1 valeurs, le tas n’est plein qu’après la première arrivée : ajoutez donc d’abord, puis lisez le sommet.
Compter à partir de la mauvaise extrémité après un tri. Dans l’ordre croissant, la k-ième plus grande valeur se trouve à l’index length-k ; l’index k-1 contient la k-ième plus petite.
Utiliser l’ordre par défaut du tas. priority_queue de C++ et BinaryHeap de Rust sont des tas max : passez greater<int> ou encapsulez les valeurs dans Reverse.

Questions fréquentes3

Pourquoi utiliser un tas min plutôt qu’un tas max pour trouver le k-ième élément le plus grand ?

La plus petite des k plus grandes valeurs est à la fois la réponse et la valeur qu’un nouvel arrivant doit dépasser, et un tas min de taille k la maintient au sommet. Un tas max contenant toutes les valeurs place la plus grande au sommet ; atteindre la k-ième valeur signifie donc en retirer k-1 et les réinsérer à chaque arrivée.

Quelle est la complexité temporelle du k-ième plus grand élément dans un flux ?

Chaque arrivée coûte O(log k) : une comparaison avec le sommet et au plus un rétablissement de la propriété du tas parmi k valeurs. La construction du tas à partir de nums coûte O(n log k), donc l’exécution complète prend un temps de O((n + m) log k) et nécessite un espace supplémentaire de O(k).

Peut-on résoudre le problème du kᵉ plus grand élément dans un flux à l’aide d’une liste triée ?

Oui. Garde toutes les valeurs triées, insère chaque arrivée à sa place à l’aide d’une recherche binaire, puis lis la valeur située à k places de la fin. La recherche est en O(log n), mais le décalage des valeurs après le point d’insertion est en O(n) par arrivée : environ 1.5 × 10^8 décalages pour 10^4 valeurs initiales et 10^4 arrivées.

def kthLargestStream(k, nums, adds):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

k = 3
nums = [7, 1, 5]
adds = [3, 9, 6, 2, 8]

Résultat attendu

[3, 5, 6, 6, 7]