Longest Consecutive Sequence

Q: Union-find peut-il résoudre le problème de la plus longue séquence consécutive ?

Oui. Fais de chaque valeur distincte un ensemble, relie x à x+1 dès que les deux sont présents, et renvoie la taille du plus grand ensemble. L’algorithme s’exécute en un temps proche de O(n) , mais il nécessite une correspondance entre les valeurs et leurs indices, des liens vers les parents et des tailles, alors que le parcours avec un ensemble de hachage fait le même travail avec un seul ensemble et deux boucles.

MoyenHachage

+10

Vous recevez un tableau d’entiers nums dans un ordre quelconque. Une séquence consécutive est un groupe de valeurs x, x+1, x+2, et ainsi de suite, chacune apparaissant quelque part dans nums. Renvoyez la longueur de la plus longue séquence 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érie 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 comporte 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.

+17 tests cachés à la soumission

Pour aller plus loin

Supposons que les valeurs arrivent une à la fois et qu’après chacune d’elles, vous devez indiquer la plus longue séquence jusqu’à présent. Pouvez-vous maintenir la réponse à jour en temps moyen O(1) par valeur ?

Indices

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

0 sur 3 ouverts

Solution

Les valeurs d’une séquence peuvent se trouver n’importe où dans le tableau, vous ne pouvez donc pas parcourir les séquences de gauche à droite. Le tri les aligne en O(n log n). Un ensemble de hachage fait mieux : il répond à la question « est-ce que x+1 est ici ? » en O(1), et si vous ne comptez qu’à partir des valeurs dont x-1 est absent, chaque valeur est parcourue une seule fois, ce qui rend la recherche complète O(n).

Comptez à partir de chaque valeur en parcourant le tableau

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Considère chaque valeur comme le début potentiel d’une séquence. À partir de x, cherche x+1 dans le tableau ; s’il s’y trouve, cherche x+2, et continue jusqu’à ce qu’une valeur manque. Le nombre de valeurs atteintes correspond à la séquence qui commence par x, et la plus grande de ces longueurs est la réponse.

C’est correct, car chaque séquence a une plus petite valeur, cette valeur se trouve dans nums, et la boucle l’essaie comme point de départ et parcourt toute la séquence. Les répétitions ne posent pas de problème : elles font simplement essayer deux fois le même point de départ.

C’est lent pour deux raisons. Chaque recherche pour savoir si une valeur est présente lit jusqu’à n valeurs, et une longue séquence est parcourue à nouveau à partir de chacun de ses éléments. Prenons 10^4 valeurs qui forment une seule séquence mélangée : les parcours totalisent environ n²/2 = 5 × 10^7 étapes, et chaque étape parcourt en moyenne la moitié du tableau. Cela représente 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.
Retourne 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éries

Intuition

Le tri place les valeurs de chaque séquence les unes à côté des autres. [40, 4, 39, 1, 3, 2, 41] devient [1, 2, 3, 4, 39, 40, 41], et les séquences se lisent de gauche à droite : de 1 à 4, puis un saut jusqu’à 39.

Parcourez les valeurs triées et gardez en mémoire la longueur de la séquence en cours. Une valeur supérieure de 1 à la précédente la prolonge. Une valeur égale à la précédente est un doublon : ignorez-la, car elle ne prolonge pas la séquence et ne la termine pas non plus. Toute autre valeur marque une interruption, et une nouvelle séquence de longueur 1 commence à cet endroit.

Le tri coûte O(n log n) et le parcours O(n). Le tri en place ne nécessite pas de tableau supplémentaire, mais réordonne les données d’entrée fournies par l’appelant ; 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. Enregistrez run dans best s'il est plus grand.
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, comptage uniquement à partir du début de chaque exécution

Intuition

Place chaque valeur dans un ensemble de hachage. Maintenant, « x+1 est-il présent ? » coûte O(1) en moyenne au lieu d’un parcours, et les répétitions sont regroupées en une seule entrée.

Parcourir à partir de chaque valeur entraînerait tout de même des répétitions : dans la suite 1, 2, 3, 4, tu ferais 3 pas à partir de 1, 2 à partir de 2 et 1 à partir de 3. Commence donc un parcours uniquement à la première valeur d’une suite. Une valeur x est la première exactement lorsque x-1 ne se trouve pas dans l’ensemble. Dans [40, 4, 39, 1, 3, 2, 41], seules 1 et 39 répondent à ce critère : à partir de 1, tu atteins 4, soit une longueur de 4, et à partir de 39, tu atteins 41, soit une longueur de 3.

Chaque valeur appartient à une seule suite, et seul le parcours commencé à la première valeur de cette suite passe par cette valeur : au total, tous les parcours effectuent donc au plus n pas. Ajoute une vérification d’appartenance par valeur et la création de l’ensemble, et le total est de O(n) en temps et de O(n) en mémoire pour l’ensemble.

Parcours l’ensemble, et non nums. Si la première valeur d’une suite de 2,500 valeurs apparaît 2,000 fois dans nums, parcourir nums fait parcourir cette suite 2,000 fois.

Algorithme

Place chaque valeur de nums dans un ensemble de hachage values, et définis best sur 0.
Pour chaque valeur x de l’ensemble, ignore-la si x-1 est dans l’ensemble : ce n’est pas la première valeur de sa séquence.
Sinon, définis end sur x et incrémente-le de 1 tant que end+1 est 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

La plupart des mauvaises réponses viennent des valeurs répétées, et la plupart des réponses lentes du fait de parcourir plusieurs fois la même suite.

Traiter une répétition comme une interruption ou comme une étape après le tri. Dans [1, 2, 2, 3], réinitialiser la suite 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 ne parcourir que les débuts de suite. La réponse est correcte, mais une suite de 10^4 valeurs nécessite 5 × 10^7 étapes : c'est le travail quadratique que l'ensemble était censé éviter.
Parcourir nums au lieu de l'ensemble lorsque des valeurs se répètent. La suite commençant par une valeur qui apparaît des milliers de fois est parcourue des milliers de fois.
Marquer les valeurs dans un tableau indexé par valeur. Les valeurs atteignent ±10^9, le tableau devrait donc contenir 2 × 10^9 entrées.

Questions fréquentes4

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

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

Pourquoi la solution avec un ensemble de hachage est-elle en O(n) alors qu’elle contient une boucle while à l’intérieur d’une boucle for ?

La boucle interne ne s’exécute qu’à partir d’une valeur dont le voisin de gauche x-1 est absent, c’est-à-dire la première valeur de sa séquence. Chaque valeur est parcourue par la marche de sa propre séquence et par aucune autre, donc toutes les boucles internes réunies effectuent au plus n étapes. La boucle externe ajoute une vérification par valeur, soit O(n) au total.

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 suites en un seul passage, en ignorant les répétitions. Cela utilise une mémoire supplémentaire de O(1), mais prend un temps de O(n log n). La solution en O(n) nécessite l’ensemble de hachage.

Union-find peut-il résoudre le problème de la plus longue séquence consécutive ?

Oui. Fais de chaque valeur distincte un ensemble, relie x à x+1 dès que les deux sont présents, et renvoie la taille du plus grand ensemble. L’algorithme s’exécute en un temps proche de O(n), mais il nécessite une correspondance entre les valeurs et leurs indices, des liens vers les parents et des tailles, alors que le parcours avec un ensemble de hachage fait le même travail avec un seul ensemble et deux boucles.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

Longest Consecutive Sequence

Fonction

Contraintes

Exemples

Indices

Solution

Comptez à partir de chaque valeur en parcourant le tableau

Trier, puis compter les séries

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

Pièges et cas limites

Questions fréquentes4

Problèmes similaires