Contar elementos distintos en un arreglo
Publicado por Camilo (2 intervenciones) el 21/04/2016 19:02:14
Buenos Días
En una pagina de juez online me encontré con el siguiente problema:
Dan una cantidad de enteros entre 0 y 9 por ejemplo 0 8 7 4 2 0 1 2 1 y después un intervalo, por ejemplo el intervalo 1 - 7 lo que hay que hacer es decir cuantos números diferentes hay en el intervalo que en este caso serian 6
entrada
El problema da un entero n entre 1 y 100000
seguido a esto hay n enteros entre 0 y 9
luego viene una linea con un entero m entre 1 y 10000
por ultimo m lineas con dos enteros a y b (1 ≤a, b ≤ n)
salida
cantidad de diferentes enteros para cada intervalo
ejemplo
entrada
5
0 0 1 8 0
3
1 1
1 5
2 4
6
4 4 4 4 4 4
2
2 4
1 3
salida
1
3
3
1
1
Mi código es el siguiente, pero el programa excede el limite de tiempo
Quedaría agradecido si me pudieran ayudar a optimizar el código o ayudarme a encontrar una solución mucho mas eficiente
En una pagina de juez online me encontré con el siguiente problema:
Dan una cantidad de enteros entre 0 y 9 por ejemplo 0 8 7 4 2 0 1 2 1 y después un intervalo, por ejemplo el intervalo 1 - 7 lo que hay que hacer es decir cuantos números diferentes hay en el intervalo que en este caso serian 6
entrada
El problema da un entero n entre 1 y 100000
seguido a esto hay n enteros entre 0 y 9
luego viene una linea con un entero m entre 1 y 10000
por ultimo m lineas con dos enteros a y b (1 ≤a, b ≤ n)
salida
cantidad de diferentes enteros para cada intervalo
ejemplo
entrada
5
0 0 1 8 0
3
1 1
1 5
2 4
6
4 4 4 4 4 4
2
2 4
1 3
salida
1
3
3
1
1
Mi código es el siguiente, pero el programa excede el limite de tiempo
Quedaría agradecido si me pudieran ayudar a optimizar el código o ayudarme a encontrar una solución mucho mas eficiente
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.io.File;
import java.io.PrintStream;
import java.util.Scanner;
public class tobbyquery {public static <T> void main(String[] args) throws Throwable {
Scanner lectura;
File f = new File("entradaC.in");
if (f.exists()) {
lectura = new Scanner(f);
System.setOut(new PrintStream(new File("salida3.out")));
} else {
lectura = new Scanner(System.in);
}while (lectura.hasNext()) {
int s = lectura.nextInt();
int[] linea = new int[s];
for (int i = 0; i < s; i++) {
linea[i] = lectura.nextInt();
}int q = lectura.nextInt();
for (int k = 0; k < q; k++) {
boolean [] bool=new boolean[10];
int inicio = lectura.nextInt() - 1;
int fin = lectura.nextInt();
int contador=0;while(inicio<fin&&contador<10){
if(!bool[linea[inicio]]){
bool[linea[inicio]]=true;
contador++;
}inicio++;
}System.out.println( contador );
} } }}Valora esta pregunta
0