Ejemplo
Para
a = [2, 3, 3, 1, 5, 2]
, la salida debería serfirstDuplicate(a) = 3
.Hay 2 duplicados: números
2
y3
. La segunda ocurrencia del3
tiene un índice menor a la segunda ocurrencia del2
, de modo que la respuesta es3
.Para
a = [2, 4, 3, 5, 1]
, la salida debería serfirstDuplicate(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