First Missing Positive

+10

On vous donne un tableau non trié d’entiers nums. Retournez le plus petit entier positif (supérieur ou égal à 1) qui n’apparaît pas dans nums. Le tableau peut contenir des nombres négatifs, des zéros, des valeurs répétées et des valeurs bien supérieures à sa longueur.

Fonction

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: les nombres entiers non triés, qui peuvent se répéter et être négatifs, nuls ou très grands
Renvoieinteger: le plus petit entier positif absent de nums

Contraintes

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Les valeurs ne sont dans aucun ordre particulier et peuvent se répéter.

Exemples

Entrée: nums = [5, -2, 1, 3, 2, 9]
Sortie: 4
Explication: 1, 2 et 3 sont tous dans le tableau et 4 n’y est pas, donc la réponse est 4. Le 5 et le 9 n’ont pas d’importance dès qu’une valeur plus petite est manquante.

Pour aller plus loin

Peux-tu trouver la réponse en temps O(n) en n’utilisant que O(1) mémoire supplémentaire ?

Indices

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

0 sur 3 ouverts

Solution

Le tri prend un temps de O(n log n) et un ensemble de hachage utilise O(n) mémoire supplémentaire. Une borne est plus avantageuse que les deux : n valeurs couvrent au plus n des nombres de 1 à n+1, donc la réponse est au plus n+1. Seules les valeurs de 1 à n comptent, et le tableau comporte n emplacements pour les enregistrer, donc la mémoire supplémentaire passe à O(1).

Essayez chaque candidat avec un balayage complet

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Testez les candidats 1, 2, 3, ... dans l’ordre. Pour chacun, parcourez tout le tableau et renvoyez le premier candidat que le parcours ne trouve pas. Grâce à la borne, vous ne testez jamais au-delà de n+1.

Lorsque le tableau contient les valeurs de 1 à n, chaque candidat est trouvé en moyenne à mi-parcours, donc n = 10^4 coûte environ n²/2 = 5 × 10^7 comparaisons.

Algorithme

Définissez candidate à 1.
Parcourez nums à la recherche d’un élément égal à candidate, en vous arrêtant au premier trouvé.
Si aucun élément ne correspond, renvoyez candidate.
Sinon, ajoutez 1 à candidate et recommencez le parcours. Vous ne dépassez jamais n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # n values cannot cover all of 1..n+1, so one of these candidates is missing
    for candidate in range(1, n + 2):
        found = False
        for num in nums:
            if num == candidate:
                found = True
                break
        if not found:
            return candidate

Marquer les valeurs de 1 à n dans un tableau d’indicateurs

Intuition

Comme la réponse est au plus n+1, ignorez toute valeur inférieure à 1 ou supérieure à n. Un tableau booléen present de longueur n+1 enregistre les autres valeurs, de sorte qu’une valeur comme 10^9 n’est jamais stockée. Renvoyez le premier v de 1 à n dont le drapeau est faux, ou n+1 si tous les drapeaux sont activés.

Dans le premier exemple, n = 6 : les drapeaux pour 1, 2, 3 et 5 sont activés, -2 et 9 sont ignorés, et le premier drapeau désactivé est 4. Deux parcours linéaires donnent un temps O(n), et les drapeaux nécessitent une mémoire O(n).

Algorithme

Créez present, n+1 indicateurs définis sur false.
Pour chaque valeur v dans nums telle que 1 ≤ v ≤ n, définissez present[v] sur true.
Retournez le premier v de 1 à n dont l’indicateur est false.
S’il n’y en a aucun, retournez n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # present[v] says whether v is in nums; only 1..n can matter
    present = [False] * (n + 1)
    for num in nums:
        if 1 <= num <= n:
            present[num] = True
    for v in range(1, n + 1):
        if not present[v]:
            return v
    return n + 1

Place chaque valeur dans son propre emplacement

Intuition

La valeur v doit se trouver à l’indice v-1. Lorsque chaque valeur de 1 à n est à sa place, le premier indice i qui ne contient pas i+1 indique la réponse.

À chaque indice, échangez la valeur avec celle de sa place tant qu’elle est comprise entre 1 et n et que sa place ne la contient pas déjà. La valeur qui revient peut elle aussi devoir être déplacée. Vérifier la place, et non i, permet d’éviter les doublons : dans [1, 1], le deuxième 1 voit un 1 à l’indice 0 et reste en place.

Dans le premier exemple, l’indice 0 envoie le 5 à sa place, puis le 2 qui revient ; plus tard, le 1 et le 3 vont à leur place, laissant [1, 2, 3, -2, 5, 9] : l’indice 3 est le premier emplacement incorrect, donc la réponse est 4.

Chaque échange place définitivement une valeur à sa place, donc les boucles internes effectuent au plus n échanges au total : temps O(n) et mémoire O(1), sauf en R, qui copie le vecteur qu’elle modifie.

Algorithme

Pour chaque indice i de 0 à n-1 :
Tant que 1 ≤ nums[i] ≤ n et que nums[nums[i]-1] ≠ nums[i], échangez nums[i] avec nums[nums[i]-1].
Après la passe de placement, trouvez le premier indice i où nums[i] ≠ i+1 et renvoyez i+1.
Si chaque emplacement contient sa propre valeur, renvoyez n+1.

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # Keep swapping until slot i holds a value that has no slot or is already home
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            home = nums[i] - 1
            nums[i], nums[home] = nums[home], nums[i]
    # The first slot that does not hold its own value names the answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Pièges et cas limites

Arrêter les échanges lorsque nums[i] == i+1 au lieu de les arrêter quand la bonne valeur est déjà à sa place. Avec [1, 1], les deux 1 s’échangent indéfiniment.
Utiliser if au lieu de while pour effectuer l’échange. Dans le premier exemple, le 2 qui revient de l’index 4 n’atteint jamais l’index 1, et tu renvoies 2 au lieu de 4.
Écrire nums[i] = nums[nums[i]-1], puis indexer à nouveau avec nums[i], ce qui lit l’index de destination après qu’il a changé. Enregistre d’abord l’index de destination.
Omettre la vérification de la plage, ce qui envoie 0, -2 ou 10^9 vers un index situé en dehors du tableau.
Renvoyer n quand chaque case est à la bonne place. Pour [4, 2, 1, 3], la réponse est 5.

Questions fréquentes3

Quelle est la complexité temporelle de First Missing Positive ?

La solution de placement s’exécute en temps O(n) avec un espace supplémentaire O(1). La boucle while se trouve à l’intérieur d’une boucle for, mais chaque échange place une valeur à son index final ; l’exécution entière effectue donc au maximum n échanges. La version avec un tableau de marqueurs s’exécute en temps O(n) et utilise une mémoire O(n), tandis que la recherche de chaque candidat est en O(n²).

Pourquoi la réponse n’est-elle jamais supérieure à n+1 ?

Les nombres de 1 à n+1 sont n+1 valeurs différentes, et un tableau de longueur n contient au plus n valeurs différentes ; il en manque donc une. La réponse est n+1 exactement lorsque le tableau contient toutes les valeurs de 1 à n.

La solution en place modifie-t-elle le tableau d’entrée ?

Oui, cela réorganise les valeurs. Si l’appelant a besoin de l’ordre d’origine, copiez d’abord le tableau, ce qui ramène la mémoire supplémentaire à O(n). Une autre méthode en place remplace chaque valeur en dehors de l’intervalle de 1 à n par n+1, puis marque la présence de v en rendant nums[v-1] négatif ; elle modifie également le tableau.

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

Test #1

Test #2

Test #3

Argument

nums = [5, -2, 1, 3, 2, 9]

Résultat attendu

First Missing Positive

Fonction

Contraintes

Exemples

Indices

Solution

Essayez chaque candidat avec un balayage complet

Marquer les valeurs de 1 à n dans un tableau d’indicateurs

Place chaque valeur dans son propre emplacement

Pièges et cas limites

Questions fréquentes3

Problèmes similaires