Rotate Array

Q: ¿Qué ocurre cuando k es mayor que la longitud del arreglo?

Cada n pasos, el array vuelve a su orden inicial, así que solo importan k mod n pasos. Rotar [10, 20, 30] 7 veces es lo mismo que rotarlo 1 vez, lo que da [30, 10, 20] . Cuando k es múltiplo de n , el array no cambia.

Q: ¿Cómo se rota un array hacia la izquierda?

Una rotación a la izquierda de k es una rotación a la derecha de n - (k mod n) . Con inversiones, invierte los primeros k mod n valores, después el resto y, luego, todo el arreglo. Ambas operaciones siguen teniendo un tiempo O(n).

MedioArrays y cadenas Dos punteros

+10

Recibes un arreglo de enteros nums y un número k. Rota el arreglo hacia la derecha k pasos: en cada paso, cada valor se mueve una posición a la derecha y el último valor vuelve al principio. Devuelve el arreglo rotado.

k puede ser mucho mayor que la longitud del arreglo.

Función

rotate(nums: integer-array, k: integer) → integer-array

numsinteger-array: el arreglo de enteros que se va a rotar
kinteger: cuántos pasos girar hacia la derecha
Devuelveinteger-array: nums rotado a la derecha k pasos

Restricciones

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
0 ≤ k ≤ 10⁹

Ejemplos

Entrada: nums = [4, 9, 1, 6, 3]k = 2
Salida: [6, 3, 4, 9, 1]
Explicación: Dos pasos hacia la derecha llevan los dos últimos valores, 6 y 3, al principio. Los otros tres valores se desplazan dos posiciones a la derecha y mantienen su orden: [6, 3, 4, 9, 1].

Para ir más allá

¿Puedes rotar in situ moviendo cada valor directamente a (i + k) mod n y llevando consigo el valor que desplaza? ¿Cuántos ciclos forma eso?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cada n pasos hacen que el arreglo vuelva al punto de partida, así que primero reduce k, que puede ser 10^9, a k mod n. Después escribe cada valor directamente en su índice final en un segundo arreglo, o consigue el mismo resultado dentro del arreglo con tres inversiones y O(1) de memoria adicional.

Copia cada valor en su nuevo índice

Intuición

Después de k pasos, el valor en el índice i queda en (i + k) mod n, así que escríbelo directamente allí sin hacer los pasos. Primero reduce k a k mod n: una rotación de n hace que cada valor vuelva a donde estaba, así que con k = 7 y n = 3 solo queda un paso.

Una pasada coloca los n valores: tiempo O(n), más memoria O(n) para el resultado. No puedes escribir en nums directamente de esta manera, porque cada escritura sobrescribiría un valor que todavía no has movido.

Algoritmo

Asigna n a la longitud de nums y reemplaza k por k mod n.
Crea un array de resultados de longitud n.
Para cada índice i, almacena nums[i] en result[(i + k) mod n].
Devuelve el resultado.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing
    result = [0] * n
    for i in range(n):
        result[(i + k) % n] = nums[i]
    return result

Tres inversiones in situ

Intuición

Divide el arreglo en A, los primeros n-k valores, y B, los últimos k. El arreglo rotado es B seguido de A, cada bloque en su orden original. Al invertir todo el arreglo, se invierten tanto el orden de los bloques como el orden dentro de cada uno, así que B queda primero, pero al revés, y lo mismo ocurre con A. Invertir cada bloque de nuevo restaura su orden interno.

Para [4, 9, 1, 6, 3] y k = 2: invertir todo da [3, 6, 1, 9, 4], invertir los dos primeros da [6, 3, 1, 9, 4] e invertir los últimos tres da [6, 3, 4, 9, 1].

cada valor se intercambia como máximo dos veces, así que el tiempo es O(n) y la memoria adicional consiste en unas pocas variables de índice (O(n) en R, que copia el vector cuando la función auxiliar de inversión lo modifica).

Algoritmo

Establece n en la longitud de nums y reemplaza k por k mod n.
Invierte todo el arreglo, índices del 0 al n-1.
Invierte el primer bloque, índices del 0 al k-1.
Invierte el segundo bloque, índices de k a n-1.
Devuelve nums.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing

    def reverse(left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    reverse(0, n - 1)  # the last k values come to the front, backwards
    reverse(0, k - 1)  # put the front block back in order
    reverse(k, n - 1)  # and the back block
    return nums

Errores comunes y casos límite

Olvidar k mod n. Con k = 10^9, rotar paso a paso nunca termina, y revertir los primeros k valores lee mucho más allá del final del arreglo.
Hacer un corte sin aplicar el módulo. En Python, nums[-k:] + nums[:-k] con k = 7 y n = 3 devuelve el arreglo sin cambios, porque ambos cortes terminan en el borde del arreglo.
Revertir en el orden equivocado. Revertir primero los dos bloques y al final el arreglo completo produce una rotación a la izquierda.
Error de una posición en el límite del bloque: el primer bloque termina en el índice k-1 y el segundo empieza en k. En Lua y R, que cuentan desde 1, los bloques son 1..k y k+1..n.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Rotate Array?

O(n) tanto para el enfoque de copia como para las tres inversiones, porque cada valor se mueve una cantidad constante de veces. Reducir primero k con k mod n evita que un k enorme importe. Rotar de un paso a la vez cuesta O(n × k) en cambio.

¿Qué ocurre cuando k es mayor que la longitud del arreglo?

Cada n pasos, el array vuelve a su orden inicial, así que solo importan k mod n pasos. Rotar [10, 20, 30] 7 veces es lo mismo que rotarlo 1 vez, lo que da [30, 10, 20]. Cuando k es múltiplo de n, el array no cambia.

¿Cómo se rota un array hacia la izquierda?

Una rotación a la izquierda de k es una rotación a la derecha de n - (k mod n). Con inversiones, invierte los primeros k mod n valores, después el resto y, luego, todo el arreglo. Ambas operaciones siguen teniendo un tiempo O(n).

def rotate(nums, k):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

nums = [4, 9, 1, 6, 3]
k = 2

Salida Esperada

[6, 3, 4, 9, 1]