Categorías
Algorithms

LeetCode – Eliminar duplicados de Sorted Array II (Java)

Seguimiento de «Eliminar duplicados»: ¿Qué pasa si se permiten duplicados como máximo dos veces?

Por ejemplo, dada la matriz ordenada A = [1,1,1,2,2,3], su función debería devolver length = 5, y A ahora es [1,1,2,2,3].

Por lo tanto, este problema también requiere manipulación de matrices en el lugar.

Solución Java 1

No podemos cambiar el tamaño de la matriz dada, por lo que solo cambiamos los primeros k elementos de la matriz que tiene duplicados eliminados.

public int removeDuplicates(int[] nums) {
    if(nums==null){
        return 0;
    }
    if(nums.length<3){
        return nums.length;
    }
 
    int i=0;
    int j=1;
/*
 
         i, j    1 1 1 2 2 3
step1    0  1      i j
step2    1  2      i   j
step3    1  3        i   j
step4    2  4          i   j
 
*/
    while(j<nums.length){
        if(nums[j]==nums[i]){
            if(i==0){
                i++;
                j++;
            }else if(nums[i]==nums[i-1]){
                j++;
            }else{    
                i++;
                nums[i]=nums[j];
                j++;
            }
        }else{
            i++;
            nums[i]=nums[j];
            j++;
        }
    }
 
    return i+1;
}

El problema con esta solución es que hay 4 casos que manejar. Si desplazamos nuestros dos puntos hacia la derecha en 1 elemento, la solución se puede simplificar como la Solución 2.

Solución Java 2

public int removeDuplicates(int[] nums) {
    if(nums==null){
        return 0;
    }
 
    if (nums.length <= 2){
        return nums.length;
    }
/*
1,1,1,2,2,3
  i j
*/
    int i = 1; // point to previous
    int j = 2; // point to current
 
    while (j < nums.length) {
        if (nums[j] == nums[i] && nums[j] == nums[i - 1]) {
            j++;
        } else {
            i++;
            nums[i] = nums[j];
            j++;
        }
    }
 
    return i + 1;
}
  LeetCode - Cambio de moneda (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 *