Java. Improve iteration speed

Question

Java. Improve iteration speed

Navigation

#1 by (2 votes)
#2 by (2 votes)

3

Example

For a = [2, 3, 3, 1, 5, 2] , the output should be    firstDuplicate(a) = 3 .

There are 2 duplicates: numbers 2 and 3 . The second occurrence of 3   has a lower rate than the second occurrence of 2 , so that the   answer is 3 .

For a = [2, 4, 3, 5, 1] , the output should be firstDuplicate(a) = -1 .

Entry / Exit

[time limit] 3000ms (java) [entry] array.integer a

Guaranteed Restrictions: 1 ≤ a.length ≤ 10^5 , 1 ≤ a[i] ≤ a.length .

[exit] integer

The element in a that occurs in the array more than once and that has   the minimum rate for its second occurrence. If there is no such   element, returns -1 .

The issue is not to find the duplicates, but to improve the speed of response, since the system that tests my algorithms, generates random data with many records, so that if you use many lines of code or the same does not is optimal, it happens that you exceed the maximum time of 3 sec when the code is tested in each random task generated by the system. I would like to know how to improve this code.

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

For more details you can see it in CodeFight

java algoritmos arreglos

asked by AndyC 27.11.2017 в 03:05

source

2 answers

2

One of the things that I see in the code that you placed is that you have a double for which makes the complexity of the algorithm is n^2 , now the problem according to what I understand is to say what is the number that appears published for the first time, which indicates that if you find it you should not keep looking. For this we can rely on data structures such as Set so that we go through the original arrangement, we dump it over the Set and every time we go to save a number we ask if it exists, if it is that will be the first number duplicated, if it does not exist it is saved.

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

In this way you get: 1. Reduce algorithmic complexity by not traversing the array twice 2. You do not evaluate all the elements of the arrangement, only the required ones

answered by 27.11.2017 в 04:41

The input string does not have the correct format. C # SQL Why | (operator or binary) truncates a decimal number?

score 2 · Accepted Answer

Since the problem does not restrict the amount of memory you use, but speed is of paramount importance, I would use this to create an array boolean size a.length to mark the numbers I am going very efficiently finding in the array a ( flags[n-1] = true ).

If when considering a number n I find that I have already marked it in a previous iteration ( if (flags[n-1]) ), then I know that this is the first duplicate number. Otherwise, if I reach the end of the loop, it means that I did not find duplicates, so I return -1 .

The speed should be optimal since

Only the a fix needs to be iterated once.
All accesses to the flags arrangement are optimal since they are made directly by the index.
It does not depend on one of the convenience classes in the standard library ( HashSet or other) that tend to create many objects, in particular because they need to convert primitive types to objects (ex: int --> Integer ) .

Code:

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

And, by the way, when determining the size of the arrangement ( new boolean[a.length] ) and the way to access the arrangement according to the number ( flags[n-1] ), I am taking into account the restrictions of the problem:

Guaranteed Restrictions: 1 ≤ a.length ≤ 10^5 , 1 ≤ a[i] ≤ a.length .