Summary Ranges

Q: Quelle est la complexité temporelle de Summary Ranges ?

O(n) . Chaque valeur est parcourue une fois, et chaque plage est écrite une fois. En dehors de la liste de sortie, l’espace supplémentaire est de O(1) : le début de la plage actuelle et un ou deux index.

FacileIntervalles Tableaux et chaînes

+10

Tu reçois un tableau trié nums d’entiers distincts. Répartis-le en un minimum d’intervalles d’entiers consécutifs, de sorte que chaque valeur appartienne à exactement un intervalle. Écris un intervalle a..b sous la forme du texte "a->b", ou sous la forme "a" lorsqu’il contient une seule valeur. Renvoie les intervalles dans l’ordre croissant.

Fonction

summaryRanges(nums: integer-array) → string-array

numsinteger-array: le tableau trié d’entiers distincts
Renvoiestring-array: les plages sous forme de texte, des valeurs les plus petites aux plus grandes

Contraintes

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums est trié par ordre croissant et ne contient aucun doublon.

Exemples

Entrée: nums = [0, 1, 2, 5, 6, 9]
Sortie: ["0->2", "5->6", "9"]
Explication: 0, 1, 2 se suivent, ils forment donc "0->2". Le saut de 2 à 5 commence une nouvelle plage, "5->6", et 9 reste seul sous la forme "9".

Entrée: nums = [-3, -1, 0, 1, 4, 7, 8]
Sortie: ["-3", "-1->1", "4", "7->8"]
Explication: -3 n’a pas de voisin (-2 manque), -1, 0, 1 forment une suite, 4 est isolé et 7, 8 terminent la liste. Les valeurs négatives fonctionnent de la même façon : -1 est suivi de -1 + 1 = 0.

+16 tests cachés à la soumission

Pour aller plus loin

Supposons que nums puisse contenir des doublons, comme [1, 2, 2, 3]. Que modifierais-tu pour qu’il affiche toujours "1->3" ?

Indices

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

0 sur 3 ouverts

Solution

Comme les valeurs sont triées et distinctes, une plage d’entiers consécutifs forme toujours une suite d’éléments voisins dans le tableau, et une plage se termine exactement là où deux éléments voisins diffèrent de plus de 1. En coupant le tableau à chaque intervalle de cette sorte, on obtient le plus petit nombre de plages, car aucune plage ne peut traverser un intervalle. Il ne reste qu’à gérer soigneusement les détails : le début de chaque suite, son dernier élément et le format du texte.

Vérifiez les deux voisins de chaque valeur

Intuition

Examinez une valeur à la fois et posez-vous deux questions. Une plage commence-t-elle ici ? Oui, si c’est la première valeur ou si la valeur précédente n’est pas inférieure de un. Une plage se termine-t-elle ici ? Oui, si c’est la dernière valeur ou si la valeur suivante n’est pas supérieure de un.

Dans [0, 1, 2, 5, 6, 9], une plage commence à 0, 5 et 9, et se termine à 2, 6 et 9. Mémorisez la valeur à laquelle la plage actuelle a commencé. Lorsqu’une plage se termine à nums[i], écrivez "start->nums[i]", ou seulement "start" lorsque la plage a commencé et s’est terminée à la même valeur, comme c’est le cas pour 9.

Chaque valeur est visitée une fois et examine deux voisines, donc le temps d’exécution est O(n). En dehors du résultat, vous ne gardez en mémoire qu’un seul début, donc l’espace supplémentaire est O(1).

Algorithme

Définissez start = nums[0].
Pour chaque indice i : si i > 0 et nums[i] != nums[i-1] + 1, définissez start = nums[i].
Si i est le dernier indice ou si nums[i+1] != nums[i] + 1, l’intervalle se termine ici.
Ajoutez "start" lorsque start == nums[i], sinon "start->nums[i]".
Renvoyez la liste après le dernier indice.

def summaryRanges(nums):
    n = len(nums)
    ranges = []
    start = nums[0]
    for i in range(n):
        # A range opens where the value before is not one less.
        if i > 0 and nums[i] != nums[i - 1] + 1:
            start = nums[i]
        # A range closes where the value after is not one more.
        if i == n - 1 or nums[i + 1] != nums[i] + 1:
            ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
    return ranges

Deux pointeurs sur chaque séquence

Intuition

Considère chaque plage comme un bloc du tableau et trouve ses deux extrémités. Le pointeur i se trouve sur la première valeur d’une plage. Le pointeur j commence à i et avance vers la droite tant que la valeur suivante est exactement supérieure de un, puis s’arrête sur la dernière valeur de la plage.

Pour [-3, -1, 0, 1, 4, 7, 8] : i ne peut pas aller au-delà de -3, car -1 n’est pas égal à -2 ; la plage est donc "-3". Ensuite, i passe à -1, et j avance sur 0 et 1, puis s’arrête avant 4 : "-1->1". Viennent ensuite "4" et "7->8". Après chaque plage, i passe à j+1, la première valeur de la suivante.

Le nombre de plages est minimal : deux valeurs séparées par un écart ne peuvent jamais appartenir à la même plage, et la méthode ne sépare qu’aux écarts. Les deux pointeurs avancent uniquement vers l’avant ; la boucle interne s’exécute donc n fois au total pour toutes les plages, ce qui maintient le temps d’exécution à O(n) et l’espace supplémentaire à O(1).

Algorithme

Définissez i = 0.
Définissez j = i, puis déplacez j vers la droite tant que j+1 < n et nums[j+1] == nums[j] + 1.
Ajoutez "nums[i]" lorsque i == j, sinon "nums[i]->nums[j]".
Définissez i = j + 1 et répétez jusqu’à ce que i dépasse la fin.
Renvoyez la liste.

def summaryRanges(nums):
    ranges = []
    n = len(nums)
    i = 0
    while i < n:
        # i is the first value of a run; push j to its last value.
        j = i
        while j + 1 < n and nums[j + 1] == nums[j] + 1:
            j += 1
        ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
        # The next run starts right after this one.
        i = j + 1
    return ranges

Pièges et cas limites

La logique tient en quelques lignes ; les erreurs se trouvent dans les cas limites.

Oublier la dernière plage. Une boucle qui écrit une plage uniquement lorsqu’elle rencontre un écart n’écrit jamais la dernière, donc [0, 1, 2, 5, 6, 9] perd son "9". Fermez aussi une plage au dernier indice.
Écrire "a->a" pour une seule valeur. Une plage d’une seule valeur s’écrit "a".
Afficher les grandes valeurs en notation scientifique. R convertit un double comme 1000000000 en 1e+09 ; convertissez les valeurs en entiers avant de les coller.

Questions fréquentes4

Quelle est la complexité temporelle de Summary Ranges ?

O(n). Chaque valeur est parcourue une fois, et chaque plage est écrite une fois. En dehors de la liste de sortie, l’espace supplémentaire est de O(1) : le début de la plage actuelle et un ou deux index.

Pourquoi couper à chaque espace donne-t-il le moins d’intervalles ?

Une plage contient des entiers consécutifs ; elle ne peut donc pas contenir deux valeurs séparées par un nombre manquant. Chaque écart dans le tableau trié doit donc séparer deux plages et, avec g écarts, il te faut au moins g+1 plages. En coupant uniquement aux endroits où se trouvent les écarts, on obtient exactement g+1.

Comment gérer une plage qui ne contient qu’un seul nombre ?

Vérifie si l’intervalle commence et se termine par la même valeur. Si c’est le cas, écris cette seule valeur, comme "9". Sinon, écris le début, la flèche et la fin, comme "5->6". Avec deux pointeurs, le test est i == j.

Les plages récapitulatives nécessitent-elles que les données d’entrée soient triées ?

Oui. La méthode compare uniquement les voisins, elle repose donc sur le fait que les entiers consécutifs se trouvent côte à côte. Pour une entrée non triée, trie-la d’abord, ce qui rend l’ensemble de la tâche O(n log n), ou place les valeurs dans un ensemble de hachage et développe chaque intervalle à partir de sa plus petite valeur, comme dans le problème de la plus longue séquence consécutive.

Python

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

Cas de test

Cas 1

Cas 2

Entrée

nums = [0, 1, 2, 5, 6, 9]

Attendu

["0->2", "5->6", "9"]