Kth Largest Element in an Array

Q: Quelle est la complexité temporelle du kᵉ plus grand élément dans un tableau ?

Le tri prend un temps de O(n log n) . Un tas min de taille k prend un temps de O(n log k) et nécessite O(k) mémoire. Quickselect avec un pivot aléatoire prend un temps de O(n) en moyenne et de O(n²) dans le pire des cas, ce qu’un pivot aléatoire rend très improbable.

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

Le tas stocke les k plus grandes valeurs rencontrées jusqu’ici, et celle que vous devez comparer puis évincer est la plus petite d’entre elles. Un tas min garde cette valeur au sommet. Un tas max ne fonctionne que si vous y insérez les n valeurs et effectuez k-1 extractions, ce qui nécessite O(n) mémoire.

Q: Dois-je utiliser un tas ou quickselect pour trouver le kᵉ plus grand élément ?

Quickselect est plus rapide en moyenne, O(n) , mais il nécessite de garder toutes les valeurs en mémoire et les réordonne. Le tas est en O(n log k) , sans mauvais cas le pire, et il fonctionne lorsque les valeurs arrivent une à une et que tu ne peux pas toutes les stocker. Lors d’un entretien, explique les deux et code celui que la question de suivi demande.

MoyenTas Tri

+10

On vous donne un tableau d’entiers nums et un entier k. Retournez la k-ième plus grande valeur de nums : la valeur à la position k, en comptant à partir de 1, une fois le tableau trié de la plus grande à la plus petite.

Les valeurs égales sont comptées séparément. Dans [5, 5, 1], la plus grande valeur est 5 et la deuxième plus grande est également 5.

Fonction

findKthLargest(nums: integer-array, k: integer) → integer

numsinteger-array: les valeurs à classer
kinteger: quelle est la plus grande valeur à renvoyer, 1 pour la plus grande
Renvoieinteger: la k-ième plus grande valeur, doublons compris

Contraintes

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Les valeurs égales comptent comme des valeurs distinctes.

Exemples

Entrée: nums = [7, 2, 9, 4, 9, 1]k = 2
Sortie: 9
Explication: Du plus grand au plus petit, les valeurs sont 9, 9, 7, 4, 2, 1. Les deux 9 comptent séparément, donc la deuxième valeur la plus grande est 9, et non 7.

Entrée: nums = [5, -3, 8, 0, 2]k = 4
Sortie: 0
Explication: Du plus grand au plus petit, les valeurs sont 8, 5, 2, 0, -3, et la quatrième d’entre elles est 0.

Entrée: nums = [6]k = 1
Sortie: 6
Explication: Avec une seule valeur et k = 1, cette valeur est la plus grande.

+15 tests cachés à la soumission

Pour aller plus loin

Les valeurs arrivent maintenant une par une. Peux-tu indiquer la médiane de toutes les valeurs vues jusqu’à présent après chaque arrivée, en O(log n) par valeur ?

Indices

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

0 sur 3 ouverts

Solution

Trier puis lire une position répond à la question, et c’est suffisamment rapide ici. Ce qu’un recruteur veut voir, c’est dans quelle mesure tu peux éviter ce tri, car tu as besoin d’une seule position, pas de toutes les n. Un tas min de taille k ne conserve que les valeurs qui peuvent encore être la réponse, et quickselect partitionne comme quicksort, mais ne suit que le côté qui contient la réponse, ce qui ramène le temps moyen à O(n).

Trier et lire une position

Intuition

La k-ième plus grande valeur est définie par l’ordre de tri : il faut donc produire cet ordre. Triée de la plus grande à la plus petite, [7, 2, 9, 4, 9, 1] devient [9, 9, 7, 4, 2, 1], et la k-ième plus grande valeur se trouve à l’index k-1. Pour k = 2, il s’agit de l’index 1, le deuxième 9. Si votre tri place les plus petites valeurs en premier, lisez plutôt l’index n-k : l’index 4 de [1, 2, 4, 7, 9, 9] contient le même 9.

Les doublons ne nécessitent aucun traitement particulier : un tri conserve chaque occurrence, qui occupe sa propre position.

Avec n = 10^4, un tri effectue environ n log n ≈ 1.3 × 10^5 comparaisons, ce qui suffit pour réussir tous les tests. Le problème, c’est qu’il ordonne les n valeurs alors qu’une seule position compte. Les deux approches suivantes effectuent moins de travail de ce type.

Algorithme

Copiez nums afin que le tableau de l’appelant reste inchangé.
Triez la copie. Utilisez une comparaison numérique ; certains langages comparent les nombres comme du texte par défaut.
Renvoyez l’index k-1 d’un ordre décroissant, ou l’index n-k d’un ordre croissant.

def findKthLargest(nums, k):
    # Largest first: the k-th largest sits at index k-1.
    ordered = sorted(nums, reverse=True)
    return ordered[k - 1]

Conserver les k plus grands éléments dans un tas min

Intuition

La k-ième plus grande valeur est la plus petite des k plus grandes valeurs. Parcourez donc nums une seule fois et ne conservez que les k plus grandes valeurs rencontrées jusque-là dans un tas min. Le sommet d’un tas min est sa plus petite valeur, ce qui correspond exactement à la réponse candidate.

Lorsqu’une valeur x arrive et que le tas contient moins de k valeurs, ajoutez-la. Sinon, comparez x au sommet. Si x n’est pas plus grande, au moins k des valeurs conservées sont aussi grandes que x : x ne peut donc jamais être la réponse et vous pouvez l’ignorer. Si x est plus grande, le sommet ne fait plus partie des k plus grandes valeurs : remplacez-le par x. Dans l’exemple 2, avec k = 4, les quatre premières valeurs remplissent le tas avec 5, -3, 8, 0 et son sommet est -3. Ensuite, 2 est supérieure à -3 et la remplace, le sommet devient 0, et 0 est la réponse.

Chaque valeur nécessite au plus une opération sur le tas en O(log k), donc la complexité totale est de O(n log k) en temps et de O(k) en mémoire. Cette méthode est plus rapide que le tri lorsque k est petit, et fonctionne sur un flux : vous n’avez jamais besoin de disposer de toutes les valeurs en même temps. Python propose heapq, Java PriorityQueue, C++ priority_queue avec greater, Go container/heap, Rust BinaryHeap avec Reverse et PHP SplMinHeap. Le code des autres langages implémente le tas dans un tableau, où les enfants de l’indice i se trouvent aux indices 2i+1 et 2i+2, ou aux indices 2i et 2i+1 en Lua et R, qui commencent à compter à 1.

Algorithme

Commence avec un tas min vide.
Pour chaque valeur x, ajoute-la tant que le tas contient moins de k valeurs.
Dès qu’il contient k valeurs, remplace la valeur en tête par x uniquement si x est supérieure à celle en tête.
Après la dernière valeur, renvoie la valeur en tête du tas.

import heapq


def findKthLargest(nums, k):
    # A min-heap of the k largest values so far; its top is the smallest of them.
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x
    return heap[0]

Sélection rapide avec un partitionnement en trois voies

Intuition

Quicksort choisit un pivot et partitionne : les valeurs plus petites à sa gauche, les plus grandes à sa droite. Après une partition, le pivot se trouve à son index final dans le tableau trié, même si aucun des deux côtés n’est encore trié. Quickselect s’appuie sur ce fait. En ordre croissant, la réponse se trouve à l’index target = n-k. Après une partition, target se trouve soit à gauche du pivot, soit sur le pivot, soit à droite de celui-ci ; tu continues donc d’un côté et élimines l’autre.

Pour [7, 2, 9, 4, 9, 1] et k = 2, target vaut 6-2 = 4. Partitionnons autour de 4 : 2 et 1 prennent les index 0 et 1, 4 prend l’index 2, et 7, 9, 9 prennent les index 3 à 5. L’index 4 est à droite, donc tu ne gardes que les index 3 à 5. Partitionne ceux-ci autour de 9 : 7 prend l’index 3 et les deux 9 prennent les index 4 et 5. L’index 4 contient un 9, donc la réponse est 9.

Utilise une partition en trois voies : les valeurs inférieures au pivot, puis celles qui lui sont égales, puis celles qui lui sont supérieures, suivies à l’aide de lt et gt. Le bloc égal [lt, gt] est à sa place dans le tableau trié ; si target se trouve à l’intérieur, tu as terminé. Avec une partition simple en deux voies, un tableau de 10^4 copies de 7 rétrécit d’une valeur à chaque tour, soit environ 5 × 10^7 étapes ; la version en trois voies répond en un seul passage.

Choisis le pivot au hasard. Une fois sur deux, il se trouve dans la moitié centrale de l’intervalle, ce qui réduit celui-ci à au plus trois quarts de sa taille ; le travail attendu correspond donc à quelques passages sur n valeurs : O(n). Le pire cas reste O(n²) si chaque pivot est une valeur extrême, et un choix fixe comme le premier élément mène à ce cas sur une entrée déjà triée. Le code travaille sur une copie, ce qui coûte O(n) en mémoire ; partitionner directement nums ramène ce coût à O(1) si tu peux modifier l’entrée.

Algorithme

Copiez nums dans a, définissez target = n-k, lo = 0 et hi = n-1.
Choisissez un pivot aléatoire dans a[lo..hi].
Partitionnez a[lo..hi] en valeurs inférieures au pivot, égales au pivot et supérieures au pivot, en laissant les valeurs égales dans a[lt..gt].
Si target < lt, définissez hi = lt-1 ; si target > gt, définissez lo = gt+1 ; sinon, renvoyez le pivot.
Recommencez à partir de l’étape 2.

import random


def findKthLargest(nums, k):
    a = list(nums)
    target = len(a) - k  # the answer's index once a is sorted smallest first
    lo, hi = 0, len(a) - 1
    while True:
        pivot = a[random.randint(lo, hi)]
        # Three-way partition of a[lo..hi]: < pivot, then == pivot, then > pivot.
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1
        # Now a[lt..gt] all equal pivot, and they are in their sorted places.
        if target < lt:
            hi = lt - 1
        elif target > gt:
            lo = gt + 1
        else:
            return pivot

Pièges et cas limites

La plupart des mauvaises réponses sont dues aux doublons et à la confusion entre les deux façons de compter les positions.

Supprimer d’abord les doublons. Le problème compte chaque occurrence : dans [7, 2, 9, 4, 9, 1] avec k = 2, la réponse est 9, mais après avoir converti le tableau en ensemble, elle devient 7.
Lire le mauvais indice. k se compte à partir de 1 : la réponse se trouve à l’indice k-1 dans un ordre décroissant et à l’indice n-k dans un ordre croissant, et non à l’indice n-k-1.
Trier les nombres comme du texte. En JavaScript et TypeScript, [10, 9, 2].sort() renvoie [10, 2, 9]. Passez (a, b) => a - b.
Utiliser un tas max de taille k. Éliminer la plus grande valeur conserve les k plus petites valeurs et renvoie la k-ième plus petite.
Utiliser Quickselect avec un partitionnement en deux parties ou un pivot fixe. La présence de nombreuses valeurs égales ou d’un tableau trié entraîne alors un coût de O(n²), ce que les grands tests incluent.

Questions fréquentes4

Quelle est la complexité temporelle du kᵉ plus grand élément dans un tableau ?

Le tri prend un temps de O(n log n). Un tas min de taille k prend un temps de O(n log k) et nécessite O(k) mémoire. Quickselect avec un pivot aléatoire prend un temps de O(n) en moyenne et de O(n²) dans le pire des cas, ce qu’un pivot aléatoire rend très improbable.

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

Le tas stocke les k plus grandes valeurs rencontrées jusqu’ici, et celle que vous devez comparer puis évincer est la plus petite d’entre elles. Un tas min garde cette valeur au sommet. Un tas max ne fonctionne que si vous y insérez les n valeurs et effectuez k-1 extractions, ce qui nécessite O(n) mémoire.

Dois-je utiliser un tas ou quickselect pour trouver le kᵉ plus grand élément ?

Quickselect est plus rapide en moyenne, O(n), mais il nécessite de garder toutes les valeurs en mémoire et les réordonne. Le tas est en O(n log k), sans mauvais cas le pire, et il fonctionne lorsque les valeurs arrivent une à une et que tu ne peux pas toutes les stocker. Lors d’un entretien, explique les deux et code celui que la question de suivi demande.

Peut-on trouver le k-ième plus grand élément en temps linéaire dans le pire des cas ?

Oui. La règle médiane des médianes choisit un pivot qui garantit d’écarter une proportion fixe des valeurs, ce qui rend la sélection O(n) dans le pire des cas, même si elle est plus lente en pratique qu’un pivot aléatoire. Avec des valeurs comprises entre -10^4 et 10^4, tu peux aussi compter le nombre d’occurrences de chaque valeur et parcourir les valeurs en partant de 10^4 jusqu’à avoir dépassé k valeurs, en O(n + 2 × 10^4) temps.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [7, 2, 9, 4, 9, 1]
k = 2

Attendu

Kth Largest Element in an Array

Fonction

Contraintes

Exemples

Indices

Solution

Trier et lire une position

Conserver les k plus grands éléments dans un tas min

Sélection rapide avec un partitionnement en trois voies

Pièges et cas limites

Questions fréquentes4

Problèmes similaires