Gire una matriz de n elementos a la derecha en k pasos.
Por ejemplo, con n = 7 y k = 3, la matriz [1,2,3,4,5,6,7] se gira a [5,6,7,1,2,3,4]. ¿De cuántas formas diferentes conoces para resolver este problema?
Solución 1 – Matriz intermedia
De una manera sencilla, podemos crear una nueva matriz y luego copiar elementos a la nueva matriz. Luego cambie la matriz original usando System.arraycopy().
public void rotate(int[] nums, int k) { if(k > nums.length) k=k%nums.length; int[] result = new int[nums.length]; for(int i=0; i < k; i++){ result[i] = nums[nums.length-k+i]; } int j=0; for(int i=k; i<nums.length; i++){ result[i] = nums[j]; j++; } System.arraycopy( result, 0, nums, 0, nums.length ); } |
El espacio es O (n) y el tiempo es O (n). Puede comprobar la diferencia entre System.arraycopy () y Arrays.copyOf ().
Solución 2 – Bubble Rotate
¿Podemos hacer esto en el espacio O (1)?
Esta solución es como una especie de burbuja.
public static void rotate(int[] arr, int order) { if (arr == null || order < 0) { throw new IllegalArgumentException("Illegal argument!"); } for (int i = 0; i < order; i++) { for (int j = arr.length - 1; j > 0; j--) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } } } |
Sin embargo, el tiempo es O (n * k).
Aquí hay un ejemplo (longitud = 7, orden = 3):
i=0 0 1 2 3 4 5 6 0 1 2 3 4 6 5 ... 6 0 1 2 3 4 5 i=1 6 0 1 2 3 5 4 ... 5 6 0 1 2 3 4 i=2 5 6 0 1 2 4 3 ... 4 5 6 0 1 2 3
Solución 3 – Inversión
¿Podemos hacer esto en el espacio O (1) y en el tiempo O (n)? La siguiente solución lo hace.
Suponiendo que se nos da {1, 2, 3, 4, 5, 6} y el orden 2. La idea básica es:
1. Divide the array two parts: 1,2,3,4 and 5, 6 2. Reverse first part: 4,3,2,1,5,6 3. Reverse second part: 4,3,2,1,6,5 4. Reverse the whole array: 5,6,1,2,3,4
public static void rotate(int[] arr, int order) { if (arr == null || arr.length==0 || order < 0) { throw new IllegalArgumentException("Illegal argument!"); } if(order > arr.length){ order = order %arr.length; } //length of first part int a = arr.length - order; reverse(arr, 0, a-1); reverse(arr, a, arr.length-1); reverse(arr, 0, arr.length-1); } public static void reverse(int[] arr, int left, int right){ if(arr == null || arr.length == 1) return; while(left < right){ int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } } |
Referencias:
1. Perlas de programación
