Escriba una función que rote una matriz entera por un número dado k. Los elementos k desde el final deben moverse hasta el comienzo de la matriz, y todos los demás elementos deben moverse hacia la derecha para hacer el espacio.
La rotación debe hacerse en el lugar.
El algoritmo no debe ejecutarse en más de O (n), donde n es el tamaño de la matriz.
También se debe utilizar una memoria constante para realizar la operación.
Por ejemplo,
si la matriz se inicializa con elementos arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}
rotar (arr, 3) dará como resultado que los elementos sean {7, 8, 9, 1, 2, 3, 4, 5, 6}
rotar (arr, 6) dará como resultado {4, 5, 6, 7, 8, 9, 1, 2, 3}
popularity-contest
array-manipulation
microbiano
fuente
fuente
Respuestas:
C (104)
Minified:
fuente
a <-- b
APL (4)
No estoy seguro de si APL realmente lo requería, pero en la implementación que he visto (lo interno de) esto tomaría un tiempo proporcional
A
y una memoria constante.fuente
{⍵⌽⍨-⍺}
o{⌽⍺⌽⌽⍵}
. En NARS2000 se puede escribir elegantemente como⌽⍢⌽
.Aquí hay una versión C larga y sin aliento de la idea de Colin.
fuente
O(log(n))
operación? Mire aby
ser 1, su bucle `j 'es s_arr / go N - estas son operaciones O (N)C
No estoy seguro de cuál es el criterio, pero como me divertí con el algoritmo, aquí está mi entrada:
Lo jugaré golf por una buena medida también; 126 bytes, se pueden acortar:
fuente
No veo muchas soluciones de C ++ aquí, así que pensé en probar esta, ya que no cuenta los caracteres.
Esta es la verdadera rotación "en el lugar", por lo que utiliza 0 espacio adicional (excepto técnicamente intercambio y 3 ints) y dado que el bucle es exactamente N, también cumple la complejidad O (N).
fuente
std::rotate
porque ese tipo de derrota el propósitoSi realiza cada uno de los posibles ciclos de rotaciones por n a su vez (hay GCD (n, len (arr)) de estos), entonces solo necesita una copia temporal única de un elemento de matriz y algunas variables de estado. Así, en Python:
fuente
cycle
variable no tiene un tamaño constante. Tendrás que generar esta matriz a medida que avanzas.C (137 caracteres)
Función
rotate
minimizada a 137 caracteres:fuente
Factor tiene un tipo incorporado para matrices rotativas
<circular>
, por lo que esta es realmente una operación O (1):Un factor menos engañoso equivalente a la impresionante solución C de Ben Voigt:
fuente
JavaScript 45
Fui para el golf de todos modos porque me gusta el golf. Está al máximo O (N) siempre que
t
sea <= tamaño de la matriz.Para manejar
t
cualquier proporción en O (N) se puede usar lo siguiente (con un peso de 58 caracteres):No regresa, edita la matriz en su lugar.
fuente
r(o,t) => rot
REBELDE - 22
Entrada: k expresado como un entero unario usando
_
como un dígito, seguido de un espacio, luego un conjunto de enteros delimitados por espacios.Salida: Un espacio, luego la matriz gira.
Ejemplo:
Estado final:
Explicación:
En cada iteración, reemplaza uno
_
y una matriz[array] + tail
contail + [array]
.Ejemplo:
fuente
O(n)
, y lo hacesn
veces.Java
Demostración aquí .
Javascript Minificado , 114 :
fuente
Haskell
Esto es en realidad θ (n), ya que la división es θ (k) y la unión es θ (nk). Aunque no estoy seguro acerca de la memoria.
fuente
Python 3
Memoria constante
O (n) complejidad de tiempo
fuente
Pitón
fuente
pitón
fuente
vb.net O (n) (no memoria constante)
fuente
Rubí
fuente
C (118)
Probablemente fue demasiado indulgente con algunas de las especificaciones. Utiliza memoria proporcional a
shift % length
. También puede girar en la dirección opuesta si se pasa un valor de desplazamiento negativo.fuente
Pitón 2, 57
Si solo
l[-n:len(l)-n]
funcionara como lo esperaría. Simplemente regresa[]
por alguna razón.fuente
¿Podría alguien verificar si esto realmente cumple con los requisitos? Creo que sí, pero no he estudiado CS (todavía).
fuente
C ++, 136
fuente
Java
Intercambie los últimos k elementos con los primeros k elementos, y luego rote los elementos restantes por k. Cuando le queden menos de k elementos al final, gírelos por k% del número de elementos restantes. No creo que nadie arriba haya tomado este enfoque. Realiza exactamente una operación de intercambio para cada elemento, hace todo en su lugar.
fuente
Perl 5 , 42 bytes
Pruébalo en línea!
La subrutina toma la distancia para rotar como el primer parámetro y una referencia a la matriz como el segundo. El tiempo de ejecución es constante en función de la distancia de rotación. El tamaño de la matriz no afecta el tiempo de ejecución. La matriz se modifica en su lugar eliminando un elemento de la derecha y colocándolo a la izquierda.
fuente