array - sorting algorithms java
¿Cómo dominar los algoritmos de modificación de matriz en el lugar? (7)
Me estoy preparando para una entrevista de trabajo de software y tengo problemas con las modificaciones de arreglos en el lugar. Por ejemplo, en el problema de out-shuffle, se intercalan dos mitades de una matriz, de modo que 1 2 3 4 5 6 7 8 se convierta en 1 5 2 6 3 7 4 8. Esta pregunta pide una solución de memoria constante (y lineal -tiempo, aunque no estoy seguro de que sea siquiera posible).
Primero pensé que un algoritmo lineal es trivial, pero luego no pude resolverlo. Luego encontré un algoritmo O(n^2) simple pero me tomó mucho tiempo. Y todavía no encuentro una solución más rápida.
Recuerdo que también tuve problemas para resolver un problema similar de las Perlas de programación de Bentley, columna 2: rotar una matriz dejada por las posiciones i (por ejemplo, abcde girado por 2 se convierte en cdeab), en el tiempo O(n) y con solo un par de bytes de espacio extra.
¿Alguien tiene consejos que me ayuden a comprender estos problemas? ¿Hay tutoriales específicos para tales preguntas? ¡Gracias!
Complementando la respuesta de Aryabhatta :
Existe un método general para "seguir los ciclos" incluso sin conocer las posiciones de inicio de cada ciclo o utilizar la memoria para conocer los ciclos visitados. Esto es especialmente útil si necesita memoria O (1).
Para cada posición i en la matriz, siga el ciclo sin mover ningún dato hasta que llegue a ...
- La posición inicial i: final del ciclo. este es un nuevo ciclo: síguelo nuevamente moviendo los datos esta vez.
- una posición más baja que i: este ciclo ya fue visitado, nada que ver con eso.
Por supuesto, esto tiene una sobrecarga de tiempo (O (n ^ 2), creo) y tiene los problemas de caché del método general de "ciclos siguientes".
En términos generales, la idea es recorrer la matriz una vez, mientras
- almacenar el valor en la posición en la que se encuentra en una variable temporal
- encontrar el valor correcto para esa posición y escribirlo
- Pase al siguiente valor, o descubra qué hacer con su valor temporal antes de continuar.
Franco,
Para la programación con bucles y matrices, nada supera el libro de texto de David Gries, La ciencia de la programación . Lo estudié hace más de 20 años y hay ideas que todavía utilizo todos los días. Es muy matemático y requerirá un esfuerzo real para dominarlo, pero ese esfuerzo te recompensará muchas veces durante toda tu carrera.
La estrategia básica con algoritmos en su lugar es determinar la regla para mover una entrada de la ranura N a la ranura M.
Entonces, tu baraja, por ejemplo. si A y B son cartas y N es el número de acelgas. Las reglas para la primera mitad del mazo son diferentes a las reglas para la segunda mitad del mazo.
// A is the current location, B is the new location.
// this math assumes that the first card is card 0
if (A < N/2)
B = A * 2;
else
B = (A - N/2) * 2 + 1;
Ahora que sabemos la regla, solo tenemos que mover cada tarjeta, cada vez que movemos una tarjeta, calculamos la nueva ubicación, luego retiramos la tarjeta que se encuentra actualmente en B. coloca A en la ranura B, luego dejamos que B sea A y volver a la parte superior del algoritmo. Cada carta movida desplaza la nueva carta, que se convierte en la siguiente carta que se moverá.
Creo que el análisis es más fácil si estamos basados en 0 en lugar de 1, por lo que
0 1 2 3 4 5 6 7 // before
0 4 1 5 2 6 3 7 // after
Así que queremos mover 1-> 2 2-> 4 4-> 1 y eso completa un ciclo, luego mover 3-> 6 6-> 5 5-> 3 y eso completa un ciclo y hemos terminado.
Ahora sabemos que la tarjeta 0 y la tarjeta N-1 no se mueven, por lo que podemos ignorarlas, así que sabemos que solo necesitamos intercambiar las tarjetas N-2 en total. Lo único pegajoso es que hay 2 ciclos, 1,2,4,1 y 3,6,5,3. cuando llegamos a la tarjeta 1 la segunda vez, necesitamos pasar a la tarjeta 3.
int A = 1;
int N = 8;
card ary[N]; // Our array of cards
card a = ary[A];
for (int i = 0; i < N/2; ++i)
{
if (A < N/2)
B = A * 2;
else
B = (A - N/2) * 2 + 1;
card b = ary[B];
ary[B] = a;
a = b;
A = B;
if (A == 1)
{
A = 3;
a = ary[A];
}
}
Ahora este código solo funciona para el ejemplo de 8 cartas, debido a eso, if prueba nos mueve de 1 a 3 cuando terminamos el primer ciclo. Lo que realmente necesitamos es una regla general para reconocer el final del ciclo y dónde ir para comenzar el siguiente.
Esa regla podría ser matemática si se le ocurre una manera, o podría hacer un seguimiento de qué lugares visitó en una matriz separada, y cuando A regresa a un lugar visitado, puede explorar hacia adelante en su matriz en busca de Primer lugar no visitado.
Para que su algoritmo en el lugar sea 0 (n), la solución deberá ser matemática.
Espero que este desglose del proceso de pensamiento sea útil para usted. Si te estuviera entrevistando, esperaría ver algo como esto en la pizarra.
Nota: como señala Moron, esto no funciona para todos los valores de N, es solo un ejemplo del tipo de análisis que un entrevistador está buscando.
Para el primero, supongamos que n es par. Tienes:
Primera mitad: 1 2 3 4
segundo: 5 6 7 8
Sea x1 = primero [1], x2 = segundo [1].
Ahora, tienes que imprimir uno de la primera mitad, uno de la segunda, uno de la primera, uno de la segunda ...
Significado primero [1], segundo [1], primero [2], segundo [2], ...
Obviamente, no guarda dos mitades en la memoria, ya que esa será la memoria O (n). Mantienes punteros a las dos mitades. ¿Ves cómo harías eso?
El segundo es un poco más difícil. Considerar:
12345
abcde
..cde
.....ab
..cdeab
cdeab
¿Notan algo? Debes notar que la pregunta básicamente te pide que muevas los primeros i caracteres al final de tu cadena, sin permitirte el lujo de copiar los últimos n - i en un búfer, luego agregar el primer i y luego devolver el búfer. Necesitas hacer con memoria O (1).
Para averiguar cómo hacer esto, básicamente se necesita mucha práctica con este tipo de problemas, como con cualquier otra cosa. La práctica hace el perfecto básicamente. Si nunca antes ha hecho este tipo de problemas, es poco probable que lo descubra. Si lo ha hecho, entonces tiene que pensar en cómo puede manipular las subcadenas y / o los índices para que resuelva su problema bajo las restricciones dadas. La regla general es trabajar tanto como sea posible y aprender tanto como sea posible para que pueda encontrar soluciones a estos problemas muy rápidamente cuando los vea, pero la solución difiere bastante de un problema a otro. No hay una receta clara para el éxito, me temo. Solo lee mucho y entiende las cosas que lees antes de seguir adelante.
La lógica para el segundo problema es la siguiente: ¿qué sucede si revertimos la subcadena [1, 2], la subcadena [3, 5] y luego las concatenamos y revocamos? Tenemos, en general:
1, 2, 3, 4, ..., i, i + 1, i + 2, ..., N
invertir [1, i] =>
i, i - 1, ..., 4, 3, 2, 1, i + 1, i + 2, ..., N
invertir [i + 1, N] =>
i, i - 1, ..., 4, 3, 2, 1, N, ..., i + 1
invertir [1, N] =>
i + 1, ..., N, 1, 2, 3, 4, ..., i - 1, i
, que es lo que querias. Escribir la función inversa usando la memoria O (1) debe ser trivial.
Un enfoque general podría ser el siguiente:
- Construya una matriz de posiciones int [] pos , tal que pos [i] se refiere a la posición (índice) de una [i] en la matriz barajada.
Reorganice la matriz original int [] a , de acuerdo con esta posición de la matriz pos .
/** Shuffle the array a. */ void shuffle(int[] a) { // Step 1 int [] pos = contructRearrangementArray(a) // Step 2 rearrange(a, pos); } /** * Rearrange the given array a according to the positions array pos. */ private static void rearrange(int[] a, int[] pos) { // By definition ''pos'' should not contain any duplicates, otherwise rearrange() can run forever. // Do the above sanity check. for (int i = 0; i < pos.length; i++) { while (i != pos[i]) { // This while loop completes one cycle in the array swap(a, i, pos[i]); swap(pos, i, pos[i]); } } } /** Swap ith element in a with jth element. */ public static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }
Como ejemplo, para el caso de outShuffle, lo siguiente sería una implementación de contructRearrangementArray ().
/**
* array : 1 2 3 4 5 6 7 8
* pos : 0 2 4 6 1 3 5 7
* outshuffle: 1 5 2 6 3 7 4 8 (outer boundaries remain same)
*/
public int[] contructRearrangementArray(int[] a)
{
if (a.length % 2 != 0) {
throw new IllegalArgumentException("Cannot outshuffle odd sized array");
}
int[] pos = new int[a.length];
for (int i = 0; i < pos.length; i++) {
pos[i] = i * 2 % (pos.length - 1);
}
pos[a.length - 1] = a.length - 1;
return pos;
}
Acerca de un tiempo O (n), O (1) algoritmo de espacio para out-shuffle
Hacer un orden aleatorio en tiempo O (n) y espacio O (1) es posible, pero es difícil . No estoy seguro de por qué la gente piensa que es fácil y le están sugiriendo que intente algo más.
El siguiente documento tiene una solución de espacio O (n) y O (1) de espacio (aunque es para inshuffle, pero hacer inshuffle hace que outshuffle sea trivial):
http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf
Acerca de un método para abordar los algoritmos de modificación de matriz en el lugar
Los algoritmos de modificación en el lugar podrían ser muy difíciles de manejar.
Consideremos una pareja:
- In-out out shuffle en tiempo lineal. Utiliza la teoría de los números.
- En el lugar de tipo de fusión, estuvo abierto durante unos años. Llegó un algoritmo pero era demasiado complicado para ser práctico. Usos contables muy complicados.
Lo siento, si esto suena desalentador, pero no hay un elixir mágico que resuelva todos los problemas de algoritmos in situ para usted. Necesita trabajar con el problema, averiguar sus propiedades e intentar explotarlas (como es el caso con la mayoría de los algoritmos).
Dicho esto, para las modificaciones de la matriz que resultan en una permutación de la matriz original, puede probar el método de following the cycles of the permutation . Básicamente, cualquier permutación se puede escribir como un conjunto de ciclos desunido (vea también la respuesta de John). Por ejemplo, la permutación:
1 4 2 5 3 6
de 1 2 3 4 5 6 se puede escribir como
1 -> 1
2 -> 3 -> 5 -> 4 -> 2
6 -> 6.
Puedes leer la flecha como ''va a''.
Entonces, para permutar la matriz 1 2 3 4 5 6 sigues los tres ciclos:
1 va a 1.
6 va a 6.
2 va a 3, 3 va a 5, 5 va a 4 y 4 va a 2.
Para seguir este ciclo largo, puedes usar una sola variable temporal. Almacena 3 en ella. Pon 2 donde estaba 3. Ahora ponga 3 en 5 y almacene 5 en la temperatura y así sucesivamente. Dado que solo utiliza el espacio de temperatura extra constante para seguir un ciclo particular, está realizando una modificación in situ de la matriz para ese ciclo.
Ahora, si te di una fórmula para calcular a dónde va un elemento, todo lo que necesitas ahora es el conjunto de elementos de inicio de cada ciclo.
Una elección juiciosa de los puntos de inicio de los ciclos puede facilitar el algoritmo. Si encuentra los puntos de partida en el espacio O (1), ahora tiene un algoritmo completo en el lugar. Aquí es donde quizás deba familiarizarse con el problema y explotar sus propiedades.
Incluso si no sabía cómo calcular los puntos de inicio de los ciclos, pero tenía una fórmula para calcular el siguiente elemento, podría usar este método para obtener un algoritmo O (n) de tiempo en el lugar en algunos casos especiales.
Por ejemplo: si conoces la matriz de enteros con signo, solo se tienen enteros positivos.
Ahora puedes seguir los ciclos, pero niega los números como un indicador de elementos "visitados". Ahora puede recorrer la matriz y elegir el primer número positivo que encuentre y seguir los ciclos para eso, haciendo que los elementos del ciclo sean negativos y continúe encontrando elementos intactos. Al final, simplemente vuelve a hacer que todos los elementos sean positivos para obtener la permutación resultante.
¡Obtienes un tiempo O (n) y un algoritmo de espacio O (1)! Por supuesto, nos "engañamos" al usar los bits de signo de los enteros de matriz como nuestro bitmap "visitado" personal.
Incluso si la matriz no era necesariamente enteros, este método (de seguir los ciclos, no el troceado de los bits de signo :-)) puede usarse para abordar los dos problemas que plantea:
The inshuffle (or out-shuffle) problem: cuando 2n + 1 es una potencia de 3, se puede demostrar (usando la teoría de números) que 1,3,3 ^ 2, etc. están en diferentes ciclos y todos los ciclos están cubiertos usando esos . Combine esto con el hecho de que la confluencia es susceptible de dividirse y conquistarse, obtiene un algoritmo de espacio O (n), O (1) (la fórmula es i -> 2 * i módulo 2n + 1). Consulte el documento anterior para más detalles.The cyclic shift an array problem: el cambio cíclico de una matriz de tamaño n por k también proporciona una permutación de la matriz resultante (dada por la fórmula i va a i + k módulo n), y también se puede resolver en tiempo lineal e Colocar utilizando el siguiente método del ciclo. De hecho, en términos del número de intercambios de elementos, este método de ciclo siguiente es mejor que el algoritmo de 3 revocaciones. Por supuesto, seguir el método del ciclo puede matar la memoria caché debido a los patrones de acceso y, en la práctica, el algoritmo de 3 reveses podría ser mejor.
En cuanto a las entrevistas, si el entrevistador es una persona razonable, observará cómo piensa y aborda el problema y no si realmente lo resuelve. Así que incluso si no resuelves un problema, creo que no debes desanimarte.