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; } |