Find Minimum in Rotated Sorted Array
Una lista de enteros distintos se ordenó en orden creciente y luego se rotó: se tomaron algunos elementos del principio, posiblemente ninguno, y se movieron al final en el mismo orden. Por ejemplo, al rotar [2, 5, 9, 11, 13, 15, 17] en 3 posiciones, se obtiene [11, 13, 15, 17, 2, 5, 9]. Se te da la lista rotada nums. Devuelve su valor más pequeño en tiempo O(log n).
Función
- numsinteger-array
- la lista rotada y ordenada de números enteros distintos
- Devuelveinteger
- el valor más pequeño de nums
Restricciones
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104- Todos los valores de
numsson distintos. numses una lista creciente rotadakposiciones, donde0 ≤ k < nums.length;k = 0la deja sin rotar.
Ejemplos
- Entrada
- nums = [11, 13, 15, 17, 2, 5, 9]
- Salida
- 2
- Explicación
- Los valores aumentan de 11 a 17 y después bajan a 2, donde comienza la segunda ejecución. La búsqueda ve 17 > 9 en el índice 3, así que el mínimo está a su derecha; después, 5 ≤ 9 y 2 ≤ 5 hacen retroceder
hihasta que el rango queda reducido al índice 4, que contiene 2.
- Entrada
- nums = [4, 7, 10, 12]
- Salida
- 4
- Explicación
- Esta lista se rotó 0 posiciones, así que sigue ordenada y el mínimo es su primer valor. Cada valor intermedio es como máximo igual al último, así que
hisigue moviéndose a la izquierda hasta llegar al índice 0, que contiene 4.
- Entrada
- nums = [30, -6, 0, 8, 19]
- Salida
- -6
- Explicación
- Se movieron cuatro valores del principio al final, así que el valor más grande, 30, ahora aparece primero y el mínimo, -6, está en el índice 1. La búsqueda reduce el rango a los índices 0 y 1, ve que 30 > -6 y mueve
loa 1.
+17 pruebas ocultas al enviar
Para ir más allá
¿Puedes devolver el k-ésimo valor más pequeño de nums en O(log n) sin ordenarlo?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
En una lista ordenada, cada valor es mayor que el anterior. La rotación rompe esa propiedad en exactamente un lugar. ¿Dónde se encuentra el valor más pequeño con respecto a ese lugar?
Compara el valor del medio con el último valor de tu rango. Si el del medio es mayor, los valores deben bajar en algún punto después de él. Si es menor, el tramo desde el medio hasta el final sube sin bajar en absoluto.
Mantén
loyhialrededor del mínimo. Cuandonums[mid] > nums[hi], mueveloamid + 1; de lo contrario, muevehiamid, ya quemidmismo podría ser el mínimo. Detente cuandolosea igual ahi.
Solución
Una lista ordenada y rotada consta de dos tramos crecientes: [11, 13, 15, 17] y después [2, 5, 9]. El mínimo es el primer valor del segundo tramo, justo después del único punto donde los valores disminuyen. Recorrer la lista permite encontrar esa disminución en O(n). Comparar un valor del medio con el último valor del intervalo indica en qué lado de la disminución está el valor del medio, así que la búsqueda binaria lo encuentra en O(log n).
Camina hasta que los valores disminuyan
Intuición
En una lista ordenada, cada valor es mayor que el anterior. Al rotar la lista, ambos tramos siguen ordenados y se crea exactamente un lugar donde esto no se cumple: el valor más grande seguido del más pequeño. Así que recórrela de izquierda a derecha y devuelve el primer valor que sea menor que su vecino de la izquierda. Si no existe tal valor, la lista se rotó 0 veces y el mínimo es nums[0].
En [11, 13, 15, 17, 2, 5, 9], el recorrido pasa por 13, 15 y 17, cada uno mayor que el valor anterior, y se detiene en el índice 4, donde 2 es menor que 17. Esto ya es mejor que tomar el mínimo de todos los valores, porque se detiene en el descenso, pero este puede estar en cualquier lugar. Cuando la rotación desplazó un elemento, como en [2, 3, 4, 5, 6, 7, 8, 1], el recorrido lee toda la lista: 5000 comparaciones para 5000 elementos, mientras que la búsqueda binaria necesita 13.
Algoritmo
- Para cada índice
idesde 1 hastan-1, comparanums[i]connums[i-1]. - Si
nums[i] < nums[i-1], devuelvenums[i]: la segunda secuencia empieza ahí. - Si el bucle termina, la lista no se rotó: devuelve
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 rotatedBúsqueda binaria en comparación con el último valor
Intuición
Mantén una promesa: el mínimo está entre lo y hi, inclusive. Al principio, ese rango abarca toda la lista. Mira el valor del medio y compáralo con nums[hi], el último valor del rango.
Si nums[mid] > nums[hi], los valores descienden en algún punto entre mid y hi, y el mínimo es el valor justo después de ese descenso, así que está a la derecha de mid: establece lo = mid + 1. De lo contrario, nums[mid] < nums[hi] (los valores son distintos), así que nums[mid..hi] asciende sin descensos. Entonces, el mínimo es nums[mid] o algún valor anterior, así que establece hi = mid. No avances más allá de mid: podría ser el mínimo. Cualquiera de los dos movimientos mantiene la promesa y reduce el rango; cuando lo coincide con hi, el único valor restante es el mínimo.
Traza el primer ejemplo, [11, 13, 15, 17, 2, 5, 9]. El rango de 0 a 6 tiene el índice medio 3, cuyo valor es 17, mayor que nums[6] = 9, así que lo pasa a ser 4. El rango de 4 a 6 tiene el índice medio 5, cuyo valor es 5, que no es mayor que 9, así que hi pasa a ser 5. El rango de 4 a 5 tiene el índice medio 4, cuyo valor es 2, que no es mayor que 5, así que hi pasa a ser 4. Devuelve nums[4] = 2.
En cada paso se reduce el rango a la mitad, así que el bucle se ejecuta como máximo unas log2(n) veces: 13 pasos para 5000 elementos, con dos índices de memoria adicional.
Algoritmo
- Establece
lo = 0yhi = n-1. - Mientras
lo < hi, calculamid = lo + (hi - lo) / 2. - Si
nums[mid] > nums[hi], establecelo = mid + 1. - De lo contrario, establece
hi = mid. - Cuando termine el bucle, devuelve
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]
Errores comunes y casos límite
El bucle tiene cuatro líneas, y cada línea tiene una versión incorrecta tentadora.
- Escribir
hi = mid - 1en la segunda rama. Esa rama se ejecuta cuandomidpodría ser el mínimo mismo. En[3, 1, 2], el valor del medio, 1, no es mayor que 2, así quehibaja a 0 y la función devuelve 3. - Iterar con
lo ≤ hi. Cuandoloes igual ahi,mides igual a ambos,nums[mid] > nums[hi]es falso yhi = midno cambia nada: el bucle nunca termina. Detente cuando el rango tenga un elemento, conlo < hi. - Comparar con
nums[lo]en lugar denums[hi]. En la lista sin rotar[1, 2, 3, 4, 5], el valor del medio, 3, es mayor quenums[0] = 1, lo que hace parecer que el descenso está a la derecha, así que la búsqueda se aleja del mínimo real en el índice 0 y devuelve 4. - Devolver
loen lugar denums[lo]. La tarea pide el valor; el índice es la respuesta a una pregunta distinta (consulta las preguntas frecuentes sobre la cantidad de rotaciones). - Suponer que la lista se rotó. Se permite una rotación de 0, y el código que busca un descenso sin una alternativa lee más allá del final o no devuelve nada. Devuelve
nums[0]cuando no haya ningún descenso.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de encontrar el mínimo en un arreglo ordenado rotado?
Tiempo O(log n) y espacio adicional O(1) con búsqueda binaria. En cada paso se conserva la mitad del rango, así que una lista de 5000 elementos necesita como máximo 13 comparaciones. El recorrido para encontrar el descenso es O(n): lee todos los elementos cuando el mínimo está al final.
¿Por qué comparar nums[mid] con nums[hi] y no con nums[lo]?
Porque nums[hi] siempre determina en qué lado está el mínimo, y nums[lo] no. Si nums[mid] > nums[hi], los valores deben estar entre mid y hi; de lo contrario, nums[mid..hi] va en aumento y el mínimo está en mid o antes. Con nums[lo], el resultado nums[mid] > nums[lo] es compatible tanto con una lista sin rotar, donde el mínimo es nums[lo], como con una lista rotada, donde está a la derecha de mid.
¿Cómo se averigua cuántas veces se rotó un arreglo ordenado?
Ejecuta la misma búsqueda binaria y devuelve lo, el índice del mínimo, en lugar de nums[lo]. Si cuentas una rotación como mover el último elemento al principio, ese índice es el número de rotaciones. Si la cuentas como mover el primer elemento al final, como hace este problema, el número es (n - lo) mod n: en [11, 13, 15, 17, 2, 5, 9], el mínimo está en el índice 4, y 7 menos 4 da los 3 valores movidos.
¿Funciona la búsqueda binaria cuando el arreglo tiene elementos duplicados?
No se mantiene sin cambios. En [2, 2, 2, 0, 2], nums[mid] puede ser igual a nums[hi], y después no se descarta ninguno de los lados. Reducir el rango con hi = hi - 1 en ese caso es seguro, porque una copia de nums[hi] permanece dentro del rango en mid, pero una lista de valores iguales con un valor menor oculto entre ellos requiere entonces O(n).
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def findMin(nums):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums = [11, 13, 15, 17, 2, 5, 9]
Esperado
2