Java - Contar elementos distintos en un arreglo

   
Vista:

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

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
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

Contar elementos distintos en un arreglo

Publicado por Drozz granverg87@gmail.com (12 intervenciones) el 22/04/2016 19:57:31
pues responid una pregunta similar en esta pagina:
http://yachingamos.com/question/contar-cuantos-diferentes-digitos-hay-en-un-numero-dependiendo-de-un-rango/

igual y te sirve de algo... saludos
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Contar elementos distintos en un arreglo

Publicado por Camilo (2 intervenciones) el 24/04/2016 12:21:45
Gracias, pero aunque el resultado se puede obtener con este código, no sería muy eficiente ya que para mirar si un numero esta en el arreglo hay que recorrerlo todo, si en el peor de los casos el arreglo es de tamaño 100000 seria necesario hacer 100000 comprobaciones.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar