Find Minimum in Rotated Sorted Array

Q: Quelle est la complexité temporelle de la recherche du minimum dans un tableau trié et décalé ?

Temps en O(log n) et espace supplémentaire en O(1) avec la recherche binaire. À chaque étape, on conserve une moitié de l’intervalle, donc une liste de 5000 éléments nécessite au maximum 13 comparaisons. Le parcours à la recherche de la rupture est en O(n) : il lit chaque élément lorsque le minimum se trouve à la fin.

Q: Pourquoi comparer nums[mid] à nums[hi] et non à nums[lo] ?

Parce que nums[hi] détermine toujours de quel côté se trouve le minimum, contrairement à nums[lo] . Si nums[mid] > nums[hi] , les valeurs doivent se situer entre mid et hi ; sinon, nums[mid..hi] est croissant et le minimum se trouve à mid ou avant. Avec nums[lo] , le résultat nums[mid] > nums[lo] correspond à la fois à une liste non pivotée, où le minimum est nums[lo] , et à une liste pivotée, où il se trouve à droite de mid .

Q: Comment déterminer combien de fois un tableau trié a été pivoté ?

Effectuez la même recherche binaire et renvoyez lo , l’indice du minimum, au lieu de nums[lo] . Si vous comptez une rotation comme le déplacement du dernier élément au début, cet indice correspond au nombre de rotations. Si vous la comptez comme le déplacement du premier élément à la fin, comme le fait ce problème, le nombre est (n - lo) mod n : dans [11, 13, 15, 17, 2, 5, 9] , le minimum se trouve à l’indice 4, et 7 moins 4 donne les 3 valeurs déplacées.

Q: La recherche binaire fonctionne-t-elle lorsque le tableau contient des doublons ?

Pas inchangé. Dans [2, 2, 2, 0, 2] , nums[mid] peut être égal à nums[hi] , et alors aucun des deux côtés ne peut être exclu. Réduire avec hi = hi - 1 dans ce cas est sûr, car une copie de nums[hi] reste dans la plage à mid , mais une liste de valeurs égales contenant une valeur plus petite cachée parmi elles coûte alors O(n) .

MoyenRecherche binaire

+10

Une liste d’entiers distincts a été triée par ordre croissant, puis pivotée : un certain nombre d’éléments, éventuellement zéro, ont été pris au début et déplacés à la fin dans le même ordre. Par exemple, [2, 5, 9, 11, 13, 15, 17] pivotée de 3 positions devient [11, 13, 15, 17, 2, 5, 9]. On vous donne la liste pivotée nums. Renvoyez sa plus petite valeur en O(log n) temps.

Fonction

findMin(nums: integer-array) → integer

numsinteger-array: la liste triée par rotation d’entiers distincts
Renvoieinteger: la plus petite valeur dans nums

Contraintes

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Toutes les valeurs de nums sont distinctes.
nums est une liste croissante pivotée d’un certain k, avec 0 ≤ k < nums.length ; k = 0 signifie qu’elle n’est pas pivotée.

Exemples

Entrée: nums = [11, 13, 15, 17, 2, 5, 9]
Sortie: 2
Explication: Les valeurs montent de 11 à 17, puis chutent à 2, où commence la deuxième séquence. La recherche constate que 17 > 9 à l’index 3, donc le minimum se trouve à sa droite ; puis 5 ≤ 9 et 2 ≤ 5 font reculer hi jusqu’à ce que la plage se réduise au seul index 4, qui contient 2.

Entrée: nums = [4, 7, 10, 12]
Sortie: 4
Explication: Cette liste a été décalée de 0, elle est donc toujours triée et le minimum est sa première valeur. Chaque valeur du milieu est inférieure ou égale à la dernière, donc hi continue de se déplacer vers la gauche jusqu’à atteindre l’index 0, qui contient 4.

Entrée: nums = [30, -6, 0, 8, 19]
Sortie: -6
Explication: Quatre valeurs ont été déplacées du début à la fin, si bien que la valeur maximale, 30, vient maintenant en premier et que la valeur minimale, -6, se trouve à l’index 1. La recherche réduit la plage aux index 0 et 1, constate que 30 > -6 et déplace lo à 1.

+17 tests cachés à la soumission

Pour aller plus loin

Peux-tu renvoyer la k-ième plus petite valeur de nums en O(log n) temps, sans la trier ?

Indices

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

0 sur 3 ouverts

Solution

Une liste triée pivotée se compose de deux séquences croissantes, [11, 13, 15, 17] puis [2, 5, 9]. Le minimum est la première valeur de la deuxième séquence, juste après le seul endroit où les valeurs diminuent. Parcourir la liste permet de trouver cette diminution en O(n). Comparer une valeur centrale à la dernière valeur de l’intervalle indique de quel côté de la diminution se trouve cette valeur centrale ; une recherche binaire permet donc de la trouver en O(log n).

Marchez jusqu’à ce que les valeurs diminuent

Intuition

Dans une liste triée, chaque valeur est supérieure à celle qui la précède. La rotation de la liste conserve le tri des deux segments et crée un seul endroit où cette propriété n’est plus respectée : la plus grande valeur suivie de la plus petite. Parcourez donc la liste de gauche à droite et renvoyez la première valeur qui est inférieure à son voisin de gauche. Si aucune valeur de ce type n’existe, la liste a été pivotée de 0 et le minimum est nums[0].

Dans [11, 13, 15, 17, 2, 5, 9], le parcours passe par 13, 15 et 17, chacune supérieure à la valeur qui la précède, puis s’arrête à l’index 4, où 2 est inférieur à 17. C’est déjà mieux que de chercher le minimum parmi toutes les valeurs, car le parcours s’arrête à la chute, mais celle-ci peut se trouver n’importe où. Lorsque la rotation a déplacé un seul élément, comme dans [2, 3, 4, 5, 6, 7, 8, 1], le parcours lit toute la liste : 5000 comparaisons pour 5000 éléments, alors que la recherche binaire en nécessite 13.

Algorithme

Pour chaque indice i de 1 à n-1, comparez nums[i] à nums[i-1].
Si nums[i] < nums[i-1], renvoyez nums[i] : la deuxième séquence commence à cet endroit.
Si la boucle se termine, la liste n’a pas été pivotée : renvoyez nums[0].

def findMin(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            return nums[i]  # the only drop: the second run starts here
    return nums[0]  # no drop: the list was not rotated

Recherche binaire par rapport à la dernière valeur

Intuition

Respecte une promesse : le minimum se trouve entre lo et hi, bornes incluses. Au départ, cette plage correspond à toute la liste. Examine la valeur du milieu et compare-la à nums[hi], la dernière valeur de la plage.

Si nums[mid] > nums[hi], les valeurs diminuent quelque part entre mid et hi, et le minimum est la valeur juste après cette baisse : il se trouve donc à droite de mid. Définis lo = mid + 1. Sinon, nums[mid] < nums[hi] (les valeurs sont distinctes), donc nums[mid..hi] est croissante et n’y contient aucune baisse. Le minimum est alors nums[mid] ou une valeur située avant, donc définis hi = mid. Ne dépasse pas mid : il peut s’agir du minimum. Chaque déplacement maintient la promesse et réduit la plage ; lorsque lo rejoint hi, la seule valeur restante est le minimum.

Suivons le premier exemple, [11, 13, 15, 17, 2, 5, 9]. La plage de 0 à 6 a pour milieu l’indice 3, dont la valeur est 17, supérieure à nums[6] = 9 ; lo devient donc 4. La plage de 4 à 6 a pour milieu l’indice 5, dont la valeur est 5, qui n’est pas supérieure à 9 ; hi devient donc 5. La plage de 4 à 5 a pour milieu l’indice 4, dont la valeur est 2, qui n’est pas supérieure à 5 ; hi devient donc 4. Renvoie nums[4] = 2.

Chaque étape divise la plage par deux ; la boucle s’exécute donc au plus environ log2(n) fois : 13 étapes pour 5000 éléments, avec deux index en mémoire supplémentaire.

Algorithme

Définissez lo = 0 et hi = n-1.
Tant que lo < hi, calculez mid = lo + (hi - lo) / 2.
Si nums[mid] > nums[hi], définissez lo = mid + 1.
Sinon, définissez hi = mid.
Lorsque la boucle se termine, renvoyez nums[lo].

def findMin(nums):
    lo, hi = 0, len(nums) - 1  # the minimum sits in nums[lo..hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the values drop after mid, so the minimum is right of it
        else:
            hi = mid      # nums[mid..hi] climbs: the minimum is at mid or left of it
    return nums[lo]

Pièges et cas limites

La boucle comporte quatre lignes, et chacune a une version incorrecte tentante.

Écrire hi = mid - 1 dans la deuxième branche. Cette branche s’exécute lorsque mid peut être le minimum lui-même. Dans [3, 1, 2], la valeur centrale 1 n’est pas supérieure à 2, donc hi passe à 0 et la fonction renvoie 3.
Utiliser une boucle avec lo ≤ hi. Une fois que lo est égal à hi, mid est égal aux deux, nums[mid] > nums[hi] est faux, et hi = mid ne change rien : la boucle ne se termine jamais. Arrête-toi lorsque la plage ne contient qu’un élément, avec lo < hi.
Comparer avec nums[lo] au lieu de nums[hi]. Dans la liste non pivotée [1, 2, 3, 4, 5], la valeur centrale 3 est supérieure à nums[0] = 1, ce qui donne l’impression que la rupture se trouve à droite ; la recherche s’éloigne donc du véritable minimum à l’index 0 et renvoie 4.
Renvoyer lo au lieu de nums[lo]. La tâche demande la valeur ; l’index répond à une autre question (voir la FAQ sur le nombre de rotations).
Supposer que la liste a été pivotée. Une rotation de 0 est autorisée, et un code qui cherche une rupture sans solution de repli lit au-delà de la fin ou ne renvoie rien. Renvoie nums[0] si aucune rupture n’existe.

Questions fréquentes4

Quelle est la complexité temporelle de la recherche du minimum dans un tableau trié et décalé ?

Temps en O(log n) et espace supplémentaire en O(1) avec la recherche binaire. À chaque étape, on conserve une moitié de l’intervalle, donc une liste de 5000 éléments nécessite au maximum 13 comparaisons. Le parcours à la recherche de la rupture est en O(n) : il lit chaque élément lorsque le minimum se trouve à la fin.

Pourquoi comparer nums[mid] à nums[hi] et non à nums[lo] ?

Parce que nums[hi] détermine toujours de quel côté se trouve le minimum, contrairement à nums[lo]. Si nums[mid] > nums[hi], les valeurs doivent se situer entre mid et hi ; sinon, nums[mid..hi] est croissant et le minimum se trouve à mid ou avant. Avec nums[lo], le résultat nums[mid] > nums[lo] correspond à la fois à une liste non pivotée, où le minimum est nums[lo], et à une liste pivotée, où il se trouve à droite de mid.

Comment déterminer combien de fois un tableau trié a été pivoté ?

Effectuez la même recherche binaire et renvoyez lo, l’indice du minimum, au lieu de nums[lo]. Si vous comptez une rotation comme le déplacement du dernier élément au début, cet indice correspond au nombre de rotations. Si vous la comptez comme le déplacement du premier élément à la fin, comme le fait ce problème, le nombre est (n - lo) mod n : dans [11, 13, 15, 17, 2, 5, 9], le minimum se trouve à l’indice 4, et 7 moins 4 donne les 3 valeurs déplacées.

La recherche binaire fonctionne-t-elle lorsque le tableau contient des doublons ?

Pas inchangé. Dans [2, 2, 2, 0, 2], nums[mid] peut être égal à nums[hi], et alors aucun des deux côtés ne peut être exclu. Réduire avec hi = hi - 1 dans ce cas est sûr, car une copie de nums[hi] reste dans la plage à mid, mais une liste de valeurs égales contenant une valeur plus petite cachée parmi elles coûte alors O(n).

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [11, 13, 15, 17, 2, 5, 9]

Attendu