Longest Consecutive Sequence

Q: Quelle est la complexité temporelle de la plus longue séquence consécutive ?

La solution avec un ensemble de hachage s’exécute en temps O(n) en moyenne et utilise O(n) de mémoire supplémentaire. Le tri et le comptage prennent O(n log n) . Rechercher dans le tableau chaque valeur suivante sans ensemble peut prendre jusqu’à O(n³) .

MoyenHachage

+10

On vous donne un tableau d’entiers nums dans un ordre quelconque. Une suite consécutive est un groupe de valeurs x, x+1, x+2, et ainsi de suite, dont chacune apparaît quelque part dans nums. Renvoyez la longueur de la plus longue suite consécutive. Une valeur qui apparaît plusieurs fois ne compte qu’une seule fois.

Fonction

longestConsecutive(nums: integer-array) → integer

numsinteger-array: les entiers, dans n’importe quel ordre, répétitions autorisées
Renvoieinteger: la longueur de la plus longue séquence de valeurs consécutives présentes dans nums

Contraintes

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Les valeurs peuvent se répéter. Les positions dans le tableau n’ont pas d’importance, seule compte la présence des valeurs.

Exemples

Entrée: nums = [40, 4, 39, 1, 3, 2, 41]
Sortie: 4
Explication: 1, 2, 3 et 4 sont tous présents, une suite de 4, même s’ils sont dispersés dans le tableau. L’autre suite, de 39 à 41, ne contient que 3 valeurs.

Entrée: nums = [7, 3, 7, 5, 6, 5]
Sortie: 3
Explication: 5, 6 et 7 forment une suite de 3. Le deuxième 7 et le deuxième 5 n’ajoutent rien, et 3 ne peut pas rejoindre la suite, car 4 manque.

Pour aller plus loin

Supposons que les valeurs arrivent une par une et qu’après chacune, tu doives indiquer la plus longue séquence jusqu’ici. Peux-tu garder la réponse à jour en O(1) en moyenne par valeur ?

Indices

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

0 sur 3 ouverts

Solution

Les valeurs d’une suite peuvent se trouver n’importe où dans le tableau. Le tri les met en ordre en O(n log n). Un ensemble de hachage répond à la question « est-ce que x+1 est ici ? » en O(1), et si tu ne comptes qu’à partir des valeurs dont x-1 est absent, chaque valeur n’est parcourue qu’une fois : O(n) au total.

Compter à partir de chaque valeur en parcourant le tableau

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Considérez chaque valeur comme un possible début de séquence. À partir de x, cherchez x+1 dans le tableau, puis x+2, jusqu’à ce qu’une valeur manque, et conservez le compte le plus élevé. Chaque séquence possède une plus petite valeur dans nums, et la boucle parcourt toute la séquence à partir de celle-ci.

Chaque recherche lit jusqu’à n valeurs, et une longue séquence est parcourue à nouveau à partir de chacun de ses éléments. Pour 10^4 valeurs formant une seule séquence mélangée, les parcours prennent environ n²/2 = 5 × 10^7 étapes, chacune parcourant en moyenne la moitié du tableau : soit environ 2.5 × 10^11 comparaisons.

Algorithme

Définis best à 0.
Pour chaque valeur start dans nums, définis current à start et length à 1.
Tant qu’un parcours de nums trouve current+1, ajoute 1 à current et à length.
Stocke length dans best si sa valeur est supérieure.
Renvoie best.

def longestConsecutive(nums):
    best = 0
    for start in nums:
        current = start
        length = 1
        # "in" on a list reads it from the front until it finds the value.
        while current + 1 in nums:
            current += 1
            length += 1
        best = max(best, length)
    return best

Trier, puis compter les séquences

Intuition

Le tri place les valeurs de chaque suite les unes à côté des autres : [40, 4, 39, 1, 3, 2, 41] devient [1, 2, 3, 4, 39, 40, 41], et les suites se lisent de gauche à droite.

Parcourez les valeurs triées et conservez la longueur de la suite en cours. Une valeur supérieure de un à la précédente la prolonge. Une répétition ne prolonge pas la suite et ne la termine pas non plus : ignorez-la. Toute autre valeur démarre une nouvelle suite de longueur 1.

Le tri coûte O(n log n) et le parcours O(n). Un tri sur place ne nécessite pas de tableau supplémentaire ; les langages qui trient une copie utilisent O(n) de mémoire.

Algorithme

Triez nums par ordre croissant.
Initialisez best et run à 1, puisque le tableau n'est jamais vide.
Pour chaque indice i à partir de 1, ignorez nums[i] s'il est égal à nums[i-1].
Si nums[i] vaut nums[i-1]+1, ajoutez 1 à run ; sinon, définissez run à 1. Stockez run dans best si sa valeur est supérieure.
Renvoyez best.

def longestConsecutive(nums):
    nums.sort()
    best = 1
    run = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            continue  # a repeat neither extends nor breaks the run
        if nums[i] == nums[i - 1] + 1:
            run += 1
        else:
            run = 1
        best = max(best, run)
    return best

Ensemble de hachage, en comptant uniquement à partir du début de chaque exécution

Intuition

Avec chaque valeur dans un ensemble de hachage, une vérification d’appartenance coûte O(1) en moyenne et les répétitions sont regroupées en une seule entrée.

Parcourir à partir de chaque valeur répéterait tout de même le travail : dans la séquence 1, 2, 3, 4, tu ferais 3 pas à partir de 1, 2 à partir de 2 et 1 à partir de 3. Parcours donc uniquement à partir de la première valeur d’une séquence, c’est-à-dire une valeur x dont le x-1 est absent. Dans l’exemple 1, seules 1 et 39 répondent à ce critère, ce qui donne des séquences de 4 et 3.

Chaque valeur appartient à une seule séquence et n’est parcourue que par le parcours de cette séquence, donc l’ensemble des parcours effectue au plus n pas. Avec une vérification par valeur, le total est de O(n) en temps et de O(n) en mémoire pour l’ensemble.

Algorithme

Place chaque valeur de nums dans un ensemble de hachage values, et initialise best à 0.
Pour chaque valeur x de l’ensemble, ignore-la si x-1 se trouve dans l’ensemble : ce n’est pas la première valeur de sa suite.
Sinon, définis end sur x et incrémente-le de 1 tant que end+1 se trouve dans l’ensemble.
Stocke end-x+1 dans best si cette valeur est plus grande.
Retourne best.

def longestConsecutive(nums):
    values = set(nums)
    best = 0
    for value in values:
        # Only a value with no left neighbour starts a run.
        if value - 1 in values:
            continue
        end = value
        while end + 1 in values:
            end += 1
        best = max(best, end - value + 1)
    return best

Pièges et cas limites

Traiter un doublon comme une interruption ou comme une étape après le tri. Dans [1, 2, 2, 3], réinitialiser la séquence au deuxième 2 donne 2, et le compter comme une étape donne 4. La réponse est 3.
Initialiser best à 0 lors du parcours trié et ne le mettre à jour qu’à l’intérieur de la boucle. Un tableau contenant une seule valeur renvoie alors 0 au lieu de 1.
Parcourir chaque valeur de l’ensemble au lieu de parcourir uniquement les débuts de séquence. Une seule séquence de 10^4 valeurs coûte alors 5 × 10^7 étapes.
Parcourir nums au lieu de l’ensemble. Si la première valeur d’une séquence de 2 500 apparaît 2 000 fois, la séquence est parcourue 2 000 fois.
Indexer un tableau par valeur. Les valeurs atteignent ±10^9, il faut donc 2 × 10^9 entrées.

Questions fréquentes3

Quelle est la complexité temporelle de la plus longue séquence consécutive ?

La solution avec un ensemble de hachage s’exécute en temps O(n) en moyenne et utilise O(n) de mémoire supplémentaire. Le tri et le comptage prennent O(n log n). Rechercher dans le tableau chaque valeur suivante sans ensemble peut prendre jusqu’à O(n³).

Peux-tu résoudre le problème de la plus longue séquence consécutive sans mémoire supplémentaire ?

Oui, si tu peux réordonner l’entrée : trie-la sur place et compte les séquences en un seul passage, en ignorant les répétitions. Cela utilise O(1) mémoire supplémentaire, mais prend un temps de O(n log n). La solution en O(n) nécessite l’ensemble de hachage.

La structure union-find peut-elle résoudre le problème de la plus longue séquence consécutive ?

Oui. Faites de chaque valeur distincte un ensemble, fusionnez x avec x+1 lorsque les deux sont présents, et renvoyez la taille du plus grand ensemble. L’algorithme s’exécute en un temps proche de O(n), mais nécessite une map associant les valeurs aux indices, des liens vers les parents et des tailles, tandis que le parcours avec un ensemble de hachage n’en nécessite qu’un.

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

Test #1

Test #2

Test #3

Argument

nums = [40, 4, 39, 1, 3, 2, 41]

Résultat attendu

Longest Consecutive Sequence

Fonction

Contraintes

Exemples

Indices

Solution

Compter à partir de chaque valeur en parcourant le tableau

Trier, puis compter les séquences

Ensemble de hachage, en comptant uniquement à partir du début de chaque exécution

Pièges et cas limites

Questions fréquentes3

Problèmes similaires