Categorías
Algorithms Interview

LeetCode – Siguiente permutación (Java)

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--;
    }
}
  LeetCode - Vocales inversas de una cadena (Java)

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *