Dada una matriz de enteros sin clasificar, encuentre el primer entero positivo faltante. Por ejemplo, dado [1,2,0] devuelve 3 y [3,4,-1,1] volver 2.
Su algoritmo debe ejecutarse en tiempo O (n) y usa espacio constante.
Análisis
Este problema se puede resolver mediante el uso de un algoritmo tipo cubo. Consideremos encontrar primero el positivo faltante y el 0 primero. El hecho clave es que el i-ésimo elemento debería ser i, por lo que tenemos:
i == A[i]
A[i]== A[A[i]]
Por ejemplo, dada una matriz {1,2,0,4}, el algoritmo hace lo siguiente:
int firstMissingPositiveAnd0(int A[]) { int n = A.length; for (int i = 0; i < n; i++) { // when the ith element is not i while (A[i] != i) { // no need to swap when ith element is out of range [0,n] if (A[i] < 0 || A[i] >= n) break; //handle duplicate elements if(A[i]==A[A[i]]) break; // swap elements int temp = A[i]; A[i] = A[temp]; A[temp] = temp; } } for (int i = 0; i < n; i++) { if (A[i] != i) return i; } return n; } |
Solución Java
Este problema solo considera números positivos, por lo que necesitamos cambiar 1 compensación. El i-ésimo elemento es i + 1.
public int firstMissingPositive(int[] A) { int n = A.length; for (int i = 0; i < n; i++) { while (A[i] != i + 1) { if (A[i] <= 0 || A[i] >= n) break; if(A[i]==A[A[i]-1]) break; int temp = A[i]; A[i] = A[temp - 1]; A[temp - 1] = temp; } } for (int i = 0; i < n; i++){ if (A[i] != i + 1){ return i + 1; } } return n + 1; } |
