3

Ejemplo

Para a = [2, 3, 3, 1, 5, 2], la salida debería ser firstDuplicate(a) = 3.

Hay 2 duplicados: números 2 y 3. La segunda ocurrencia del 3 tiene un índice menor a la segunda ocurrencia del 2, de modo que la respuesta es 3.

Para a = [2, 4, 3, 5, 1], la salida debería ser firstDuplicate(a) = -1.

Entrada/Salida

[tiempo límite] 3000ms (java) [entrada] array.integer a

Restricciones garantizadas: 1 ≤ a.length ≤ 10^5, 1 ≤ a[i] ≤ a.length.

[salida] integer

El elemento en a que ocurre en el arreglo más de una vez y que tiene el índice mínimo para su segunda ocurrencia. Si no existe ningún tal elemento, devuelve -1.

El asunto no es encontrar los duplicados, sino en mejorar la velocidad de respuesta, ya que el sistema que prueba mis algoritmos, genera datos aleatorios con muchísimos registros, de tal forma, que si usas muchas lineas de código o el mismo no es optimo, sucede que te excedes del tiempo maximo de 3 seg cuando el codigo es probado en cada tarea aleatoria generada por el sistema. Me gustaria conocer como mejorar este codigo.

int firstDuplicate(int[] a) {
    int numero = -1; //coloco un valor por defecto
    int indice = 100000; //agrego un valor maximo
    int i = 0; // y un contador


    for(int valor : a){// recorro todos los valores del registro que pueden ser muchos
       if(i >= indice) break; // si el indice del numero es igual al valor de recorrido, termina el analisis.
       if( numero != a[i] ){ // solo si el vecino no es igual lo analizo

           for(int n=(i+1); n<a.length; n++){ // cada vez que analizon un valor, desde alli analizo el resto de los vecino para ver si hay duplicados
                  if(valor == a[n] && n < indice){ // si el valor esta duplicado pero el indice es menor al duplicado anterior. Entonces lo guardas.
                      indice = n;
                      numero = valor;
                      break;
                  }
            }
       } 

        i++;
    }

    return numero;
}

Para mas detalle pueden verlo en CodeFight

1
  • 1
    ¿Hace falta la descripción en inglés? Yo la eliminaría. La traducción está bien, no creo que aporte nada diferente,
    – Mariano
    Commented el 27 nov. 2017 a las 14:57

2 respuestas 2

2

Siendo que el problema no restringe la cantidad de memoria que usas, sino que la velocidad es de importancia primordial, aprovecharía esto para crear un arreglo boolean de talla a.length para ir marcando de forma muy eficiente los números que voy encontrando en el arreglo a (flags[n-1] = true).

Si al considerar un número n encuentro que ya lo he marcado en una iteración anterior (if (flags[n-1])), entonces sé que ese es el primer número duplicado. De lo contrario, si llego al final del bucle, quiere decir que no encontré duplicados, entonces devuelvo -1.

La velocidad debería ser óptima ya que

  • Solo se necesita iterar el arreglo a una sola vez.
  • Todos los accesos al arreglo flags son óptimos ya que se hacen directamente por el índice.
  • No depende de una de las clases de conveniencia en la librería estándar (HashSet u otro) que tienden a crear muchos objetos, en particular debido a que necesitan convertir los tipos primitivos a objetos (ej.: int --> Integer).

Código:

int firstDuplicate(int[] a) {
    boolean[] flags = new boolean[a.length];

    for(int n : a) {
        if (flags[n-1]) return n;
        flags[n-1] = true;
    }

    return -1;
}

Y, de paso, al determinar la talla del arreglo (new boolean[a.length]) y la forma de acceder el arreglo según el número (flags[n-1]), estoy tomando en cuenta las restricciones del problema:

Restricciones garantizadas: 1 ≤ a.length ≤ 10^5, 1 ≤ a[i] ≤ a.length.

1
  • Muy buena idea. Porque el asunto es encontrar la primera ocurrencia de cualquier numero pero solo se toma la ocurrencia del numero que tenga el indice mas bajo entre todas las ocurrencias encontradas
    – AndyC
    Commented el 27 nov. 2017 a las 18:35
2

Una de las cosas que veo en el código que colocaste es que tienes un doble for lo cual hace que la complejidad del algoritmo sea de n^2, ahora el problema de acuerdo a lo que entiendo es decir cual es el número que aparece dublicado por primera vez, lo cual indica que si lo encuentras no deberias seguir buscando. Para esto nos podemos apoyar en estucturas de datos como el Set de forma que recorramos el arreglo original, lo volcamos sobre el Sety cada vez que vayamos a guardar un número preguntamos si existe, en caso afirmativo ese será el primer número duplicado, en caso que no exista se guarda.

int firstDuplicate(int[] a) {
  int salida = -1;
  Set<Integer> duplicados = new TreeSet();
  for(int n : a){
    if(duplicados.contains(n)){
      salida = n;
      break;
    }else{
      duplicados.add(n);
    }
  }
  return salida;
}

De esta forma obtienes: 1. Reducir la complejidad algorítmica al no recorrer el arreglo dos veces 2. No evaluas todos los elementos del arreglo, solo los requeridos

7
  • Buena respuesta. Reduce la complejidad, pero al decir que se recorre una sola vez, no estás considerando que las operaciones del TreeSet también agregan complejidad. De Class TreeSet<E>, "This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains)".
    – Mariano
    Commented el 27 nov. 2017 a las 4:51
  • Si quisieras mejorarlo aún más, podrías olvidarte del .contains(). El método TreeSet.add() devuelve false si ya estaba el elemento. Podrías reducirlo a for(int n : a){if(!duplicados.add(n)){return n}}.
    – Mariano
    Commented el 27 nov. 2017 a las 5:22
  • 1
    Gracias por complementar la respuesta @Mariano, si bien la lectura del TreeSet tiene complejidad log(n) la complejidad del algoritmo sería de n*log(n) y no de n^2 que sería la tener un doble for. Y por la respuesta del TreeSet.add() genial, no me habia percatado.
    – isaac
    Commented el 27 nov. 2017 a las 13:49
  • 1
    @Mariano: No estoy tan seguro que sea mas eficiente en memoria. El problema es que las colecciones de Java no son capaces de trabajar directamente con los tipos primitivos como int. De modo que a cada Add, hay una conversión de int a Integer (autoboxing) que resulta en un objeto mas en el heap (a menos que el numero <= 127, numeros en el cache de Integer). Si los genéricos de Java pudieran manejar los tipos primitvos como lo hace C# por ejemplo, entonces sería mucho mas eficiente con la memoria.
    – sstan
    Commented el 28 nov. 2017 a las 1:54
  • 1
    @sstan entiendo, hay casos en los que juega en contra el autoboxing. Apuntaba más bien al teórico, dónde ir creando una colección, populada con cada elemento recorrido usa menos memoria que un array de N elementos (con un N grande).
    – Mariano
    Commented el 28 nov. 2017 a las 1:59

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.