Next Permutation

Q: Quelle est la complexité temporelle de la permutation suivante ?

O(n) . Un parcours depuis la droite trouve le pivot, un deuxième trouve la valeur à échanger avec lui, et une inversion suffit à corriger le suffixe. La mémoire supplémentaire est de O(1) , puisque tout se passe à l’intérieur du tableau.

MoyenTableaux et chaînes Deux pointeurs

+10

On te donne un tableau d’entiers nums, et certaines valeurs peuvent se répéter. Imagine tous les arrangements distincts de ces valeurs, triés dans l’ordre lexicographique : compare deux arrangements au premier indice où ils diffèrent, et celui qui a la plus petite valeur à cet indice vient en premier. Renvoie l’arrangement qui vient juste après nums dans cet ordre.

Si nums est déjà le plus grand arrangement, il n’y en a pas après : renvoie le plus petit, c’est-à-dire les valeurs triées par ordre croissant. Vise un temps d’exécution en O(n) et une mémoire supplémentaire en O(1).

Fonction

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

numsinteger-array: l’agencement actuel des valeurs
Renvoieinteger-array: l’arrangement suivant dans l’ordre lexicographique, ou les valeurs triées par ordre croissant si nums est le plus grand

Contraintes

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 1000

Exemples

Entrée: nums = [2, 5, 4, 1]
Sortie: [4, 1, 2, 5]
Explication: La queue 5, 4, 1 est décroissante, donc le 2 qui la précède doit augmenter. La plus petite valeur de la queue supérieure à 2 est 4 ; place-le là et mets le reste dans l’ordre croissant : [4, 1, 2, 5].

Entrée: nums = [3, 2, 2, 1]
Sortie: [1, 2, 2, 3]
Explication: Le tableau entier est décroissant, c’est donc le plus grand arrangement de 3, 2, 2 et 1. La réponse revient au plus petit, [1, 2, 2, 3].

Entrée: nums = [1, 5, 1]
Sortie: [5, 1, 1]
Explication: Le premier 1 doit augmenter. Le dernier 1 lui est égal, il n’est donc pas plus grand ; la seule valeur qui peut le remplacer est 5, ce qui donne [5, 1, 1].

Pour aller plus loin

Comment trouver plutôt l’arrangement précédent, celui qui vient juste avant nums dans l’ordre lexicographique ?

Solution

Un suffixe décroissant est déjà aussi grand que ses valeurs le permettent, donc l’arrangement suivant modifie la valeur qui le précède immédiatement, le pivot. Augmente le pivot de la plus petite quantité possible, puis rends le suffixe aussi petit que possible. Cela nécessite deux parcours depuis la droite et une inversion, à l’intérieur du tableau.

Classer les éléments dans l’ordre

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Construisez les arrangements en profondeur à partir des valeurs triées, en essayant toujours d’abord la plus petite valeur inutilisée. Cela les produit dans l’ordre lexicographique, donc le premier qui est strictement supérieur à nums est la réponse ; s’il n’y en a aucun, renvoyez les valeurs triées. Les valeurs répétées produisent certains arrangements deux fois, comme dans 115, 151, 115, 151, 511, 511 pour [1, 1, 5], mais une copie ne fait que répéter un arrangement déjà construit, donc le premier arrangement supérieur reste le suivant.

Le nombre augmente comme n! : 12 valeurs distinctes donnent 479,001,600 arrangements.

Algorithme

Trie une copie de nums dans pool.
Construis les arrangements en profondeur, en choisissant les éléments inutilisés de pool de gauche à droite.
Lorsqu’un arrangement est complet, compare-le à nums position par position.
Renvoie le premier arrangement qui est supérieur à nums.
Si aucun n’est supérieur, renvoie pool.

def nextPermutation(nums):
    n = len(nums)
    pool = sorted(nums)  # taking the smallest unused value first gives sorted order
    used = [False] * n
    current = []

    def build():
        # True once current holds the first arrangement greater than nums
        if len(current) == n:
            return current > nums  # Python compares lists in dictionary order
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(pool[i])
                if build():
                    return True
                current.pop()
                used[i] = False
        return False

    if build():
        return current
    return pool  # nothing is greater: nums was the largest arrangement

Trouvez le pivot, échangez, inversez le suffixe

Intuition

Le pivot est la première valeur en partant de la droite qui est inférieure à sa voisine de droite : le 2 dans [2, 5, 4, 1]. C’est la position la plus à droite qui peut augmenter, et augmenter la position possible la plus à droite permet de garder l’augmentation minimale.

Échangez le pivot avec la plus petite valeur du suffixe qui lui est strictement supérieure. Le suffixe est décroissant, donc il s’agit de la valeur la plus à droite qui est supérieure au pivot : 4, ce qui donne [4, 5, 2, 1]. Le suffixe reste décroissant, car l’ancien pivot se place là où se trouvait 4. Maintenant que le début est plus grand, le suffixe doit être aussi petit que possible, dans l’ordre croissant ; inverser une séquence décroissante permet d’obtenir cela : [4, 1, 2, 5].

En l’absence de pivot, le tableau est dans l’ordre le plus grand, et l’inverser entièrement donne le plus petit. Chaque étape correspond à un parcours ou à une inversion : temps O(n) et mémoire O(1), bien que la version R renvoie une copie de O(n).

Algorithme

Définissez i sur n-2 et déplacez-le vers la gauche tant que nums[i] ≥ nums[i + 1].
Si i ≥ 0, définissez j sur n-1 et déplacez-le vers la gauche tant que nums[j] ≤ nums[i], puis échangez nums[i] et nums[j].
Inversez la partie allant de i + 1 jusqu'à la fin à l'aide de deux indices qui avancent l'un vers l'autre.
Renvoyez nums.

def nextPermutation(nums):
    n = len(nums)
    # 1. the pivot is the last index whose value is smaller than the next one
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2. swap it with the rightmost value that is larger than it
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 3. the suffix after the pivot is falling: reverse it to make it rising
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

Pièges et cas limites

Utiliser > au lieu de ≥ dans la recherche du pivot. Dans [3, 2, 2, 1], la paire 2, 2 n’est pas une montée, et s’arrêter là sélectionne un pivot qui ne peut pas augmenter.
Échanger avec une valeur égale au pivot. Dans [1, 5, 1], échanger les deux 1 ne change rien ; recherchez une valeur strictement supérieure.
Échanger avec la plus grande valeur du suffixe. Dans [2, 5, 4, 1], cela place 5 devant et ignore tous les arrangements commençant par 4.
Ignorer le cas sans pivot. Le plus grand arrangement doit revenir trié, en inversant tout le tableau.
En Rust, un indice usize commençant à n-2 déclenche une panique lorsque n = 1, et reculer au-delà de 0 déclenche une panique lorsqu’il n’y a pas de pivot. Utilisez un indice signé ou comptez à partir de 1.

Questions fréquentes3

Quelle est la complexité temporelle de la permutation suivante ?

O(n). Un parcours depuis la droite trouve le pivot, un deuxième trouve la valeur à échanger avec lui, et une inversion suffit à corriger le suffixe. La mémoire supplémentaire est de O(1), puisque tout se passe à l’intérieur du tableau.

Pourquoi inverses-tu le suffixe au lieu de le trier ?

Après l’échange, le suffixe est toujours décroissant, donc l’inverser le trie déjà par ordre croissant. Une inversion prend O(n) ; un tri donne le même résultat en O(n log n).

Next Permutation fonctionne-t-il avec des valeurs dupliquées ?

Oui, tant que les deux comparaisons ne considèrent pas les valeurs égales comme plus grandes. La recherche du pivot ignore les voisins égaux avec ≥, et la recherche de l’élément à échanger ignore les valeurs égales au pivot avec ≤. Ensuite, [1, 5, 1] devient [5, 1, 1], le prochain arrangement distinct.

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

Test #1

Test #2

Test #3

Argument

nums = [2, 5, 4, 1]

Résultat attendu

[4, 1, 2, 5]