Implementar la siguiente permutación, que reorganiza los números en la siguiente permutación lexicográficamente mayor de números.
Si tal arreglo no es posible, debe reorganizarlo en el orden más bajo posible (es decir, clasificado en orden ascendente). El reemplazo debe estar en su lugar, no asigne memoria adicional.
Aquí hay unos ejemplos. Las entradas están en la columna de la izquierda y sus salidas correspondientes están en la columna de la derecha.
1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
Análisis
Los pasos para resolver este problema:
1) escanee de derecha a izquierda, encuentre el primer elemento que sea menor que el anterior.
4 5 6 3 2 1 | p
2) escanee de derecha a izquierda, encuentre el primer elemento que sea mayor que p.
4 5 6 3 2 1 | q
3) intercambiar pyq
4 5 6 3 2 1 swap 4 6 5 3 2 1
4) elementos inversos [p+1, nums.length]
4 6 1 2 3 5
Solución Java
public void nextPermutation(int[] nums) { //find first decreasing digit int mark = -1; for (int i = nums.length - 1; i > 0; i--) { if (nums[i] > nums[i - 1]) { mark = i - 1; break; } } if (mark == -1) { reverse(nums, 0, nums.length - 1); return; } int idx = nums.length-1; for (int i = nums.length-1; i >= mark+1; i--) { if (nums[i] > nums[mark]) { idx = i; break; } } swap(nums, mark, idx); reverse(nums, mark + 1, nums.length - 1); } private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } private void reverse(int[] nums, int i, int j) { while (i < j) { swap(nums, i, j); i++; j--; } } |