Remove Duplicates from Sorted Array

Q: Comment supprimer les doublons en place sans mémoire supplémentaire ?

Gardez un index d’écriture k à côté de l’index de lecture. Les premiers emplacements k contiennent les valeurs distinctes rencontrées jusqu’ici. Lorsque la valeur lue diffère de nums[k-1] , copiez-la dans nums[k] et incrémentez k . L’index d’écriture ne dépasse jamais l’index de lecture, ainsi rien n’est écrasé avant d’avoir été lu.

FacileDeux pointeurs

+10

On vous donne un tableau d’entiers nums trié par ordre non décroissant, de sorte que les valeurs égales se trouvent côte à côte. Renvoyez les valeurs distinctes de nums, chacune une seule fois, dans l’ordre où elles apparaissent. Par exemple, [2, 2, 5] donne [2, 5].

Fonction

removeDuplicates(nums: integer-array) → integer-array

numsinteger-array: les entiers, triés par ordre non décroissant
Renvoieinteger-array: les valeurs distinctes de nums, par ordre croissant

Contraintes

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums est trié par ordre non décroissant.

Exemples

Entrée: nums = [1, 1, 2, 3, 3, 3]
Sortie: [1, 2, 3]
Explication: 1 apparaît deux fois et 3 trois fois. En gardant un exemplaire de chaque, on obtient [1, 2, 3].

Entrée: nums = [-2, 0, 0, 5]
Sortie: [-2, 0, 5]
Explication: Seul 0 se répète. Les valeurs négatives fonctionnent de la même manière, donc la réponse est [-2, 0, 5].

Entrée: nums = [7, 7, 7]
Sortie: [7]
Explication: Chaque valeur est 7, donc il ne reste qu’un seul 7.

+15 tests cachés à la soumission

Pour aller plus loin

Peux-tu le faire avec une mémoire supplémentaire de O(1), en modifiant nums sur place au lieu de créer un deuxième tableau ?

Indices

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

0 sur 3 ouverts

Solution

Supprimer les doublons d’un tableau arbitraire signifie mémoriser chaque valeur déjà rencontrée. Un tableau trié rend cela inutile : les copies d’une valeur sont voisines, donc une valeur est nouvelle exactement lorsqu’elle diffère de la dernière que vous avez conservée. Le problème se réduit ainsi à un seul parcours avec deux index et sans mémoire supplémentaire.

Mémoriser les valeurs déjà vues dans un ensemble de hachage

Intuition

Parcourez nums et gardez un ensemble des valeurs que vous avez déjà ajoutées à la réponse. Lorsqu’une valeur ne figure pas dans l’ensemble, ajoutez-la à la réponse et à l’ensemble ; si elle y figure, ignorez-la. Pour [1, 1, 2, 3, 3, 3], la réponse devient [1], puis [1, 2], puis [1, 2, 3], et chaque copie suivante est ignorée.

Chaque valeur est ajoutée la première fois qu’elle apparaît, et jamais plus, dans l’ordre où vous la rencontrez : la réponse est donc correcte. Cette approche n’utilise jamais le fait que nums est trié ; elle fonctionnerait avec n’importe quel tableau.

Les recherches dans un ensemble prennent O(1) en moyenne, donc le parcours prend O(n) en temps, mais l’ensemble et la réponse peuvent chacun contenir n valeurs : O(n) d’espace supplémentaire. En C, en l’absence d’ensemble intégré, un tableau de marqueurs pour les 2 × 10^4 + 1 valeurs possibles fait le même travail.

Algorithme

Crée un ensemble vide seen et une liste vide result.
Pour chaque valeur de nums, vérifie si elle se trouve dans seen.
Si ce n’est pas le cas, ajoute-la à seen et ajoute-la à la fin de result.
Renvoie result.

def removeDuplicates(nums):
    seen = set()
    result = []
    for num in nums:
        if num not in seen:
            seen.add(num)
            result.append(num)
    return result

Compacter sur place avec un pointeur d’écriture

Intuition

Dans une entrée triée, toutes les occurrences d’une valeur forment un seul groupe ; une valeur est donc nouvelle exactement lorsqu’elle diffère de la dernière valeur conservée. Une seule comparaison suffit, pas besoin d’un ensemble.

Utilise deux index. L’index de lecture i parcourt chaque valeur. L’index d’écriture k marque la fin de la partie conservée : nums[0] à nums[k-1] contient toujours les valeurs distinctes trouvées jusqu’ici. Commence avec k = 1, puisque la première valeur est toujours conservée. Lorsque nums[i] diffère de nums[k-1], copie-la dans nums[k] et incrémente k.

Avec [1, 1, 2, 3, 3, 3] : i = 1 lit un deuxième 1 et rien ne se passe. i = 2 lit 2, qui diffère de nums[0] = 1 ; cette valeur est donc écrite à l’index 1 et k passe à 2. i = 3 écrit 3 à l’index 2 et k passe à 3. Les deux derniers 3 correspondent à nums[2] et sont ignorés. Les trois premiers emplacements contiennent maintenant [1, 2, 3].

L’écriture ne dépasse jamais la lecture, car k est toujours inférieur ou égal à i ; tu n’écrases donc jamais une valeur avant de l’avoir lue. Un seul parcours prend un temps de O(n) et, en plus des valeurs retournées, tu utilises deux entiers : un espace supplémentaire de O(1).

Algorithme

Définissez k = 1 : nums[0] est toujours conservé.
Parcourez i de 1 jusqu’au dernier indice.
Si nums[i] est différent de nums[k-1], définissez nums[k] = nums[i] et ajoutez 1 à k.
Renvoyez les k premières valeurs de nums.

def removeDuplicates(nums):
    # nums[0:k] holds the distinct values found so far, in order.
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return nums[:k]

Pièges et cas limites

Le pointeur d’écriture est simple, et ses erreurs concernent la valeur à laquelle vous comparez.

Comparer nums[i] à nums[i+1] alors que i va jusqu’au dernier indice. La dernière comparaison lit au-delà de la fin du tableau.
Initialiser k à 0. La première valeur est alors comparée à nums[-1], qui est hors limites ou, en Python, désigne le dernier élément.
Renvoyer le tableau entier au lieu de ses k premières valeurs. Les éléments de fin contiennent encore d’anciennes valeurs : [1, 1, 2] serait donc renvoyé sous la forme [1, 2, 2].
Construire la réponse en parcourant un ensemble de hachage. Dans la plupart des langages, un ensemble de hachage ne conserve aucun ordre, les valeurs peuvent donc sortir dans le désordre ; ajoutez plutôt chaque valeur à une liste lorsque vous la rencontrez pour la première fois.
En Lua et en R, les tableaux commencent à 1. La partie conservée va de nums[1] à nums[k], et la comparaison se fait avec nums[k], et non avec nums[k-1].

Questions fréquentes4

Quelle est la complexité temporelle de la suppression des doublons d’un tableau trié ?

La solution avec un pointeur d’écriture lit chaque valeur une seule fois, elle s’exécute donc en O(n) temps. En plus des valeurs qu’elle renvoie, elle utilise O(1) espace supplémentaire : deux index.

Pourquoi le tableau doit-il être trié ?

Le tri regroupe toutes les occurrences d’une valeur dans une séquence, donc une valeur est nouvelle exactement lorsqu’elle diffère de la dernière valeur conservée. Dans un tableau non trié, une occurrence peut apparaître loin de la première, et tu as besoin d’un ensemble de hachage pour mémoriser chaque valeur rencontrée, ce qui nécessite un espace supplémentaire de O(n).

Comment supprimer les doublons en place sans mémoire supplémentaire ?

Gardez un index d’écriture k à côté de l’index de lecture. Les premiers emplacements k contiennent les valeurs distinctes rencontrées jusqu’ici. Lorsque la valeur lue diffère de nums[k-1], copiez-la dans nums[k] et incrémentez k. L’index d’écriture ne dépasse jamais l’index de lecture, ainsi rien n’est écrasé avant d’avoir été lu.

Comment autoriser chaque valeur au maximum deux fois ?

Comparez avec la valeur située deux places en arrière dans la partie conservée au lieu d’une seule : copiez nums[i] lorsque k < 2 ou lorsqu’elle diffère de nums[k-2]. Si elle est égale à nums[k-2], la partie conservée se termine déjà par deux exemplaires de cette valeur. La même idée permet d’en conserver au plus m exemplaires avec nums[k-m].

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [1, 1, 2, 3, 3, 3]

Attendu

[1, 2, 3]