Struttura dati per un'operazione più veloce contiene()?

Question

Nel problema, analizzo l'input (numero intero) e controllo simultaneamente se esiste nella struttura dati, altrimenti lo aggiungo.

ingresso è - 2 numeri interi separati da uno spazio di dimensioni> = 1 e < = 1000000

Ho provato ad utilizzare HashMap, TreeMap (put() e containsValue() metodo) - ma sembra che stanno prendendo troppo tempo. (5 su 10 casi di test superano termine)

Quando si utilizza ArrayList (add() e contiene() metodo) - (4 di 10 casi di test superato il limite di tempo)

Queste operazioni devono essere eseguito all'interno del secondo ciclo, all'interno di una condizione if.

iterazioni può varia come segue: -

1 ° ciclo - 1 a 10

secondo ciclo - Da 1 a 100000

quindi immagino per una maggiore iterazione ordine nel secondo ciclo supera il tempo limite.

Esiste un altro modo per eseguire questo compito in minor tempo.

Problema:

A Monaco incontra N stagni e ad ogni stagno viene trovato un fooditem (ingresso 1) e un pokemon (ingresso 2).

Il monaco può sfamare l'oggetto al suo stagno per il Pokemon allo stagno se il tipo corrisponde. Il monaco potrebbe dover portare con sé alcuni prodotti alimentari prima di partire per dare da mangiare a tutti i Pokemon. Aiutalo a trovare il numero di oggetti che deve portare, per essere in grado di attraversare la terra in sicurezza.

Spiegazione

a prima Stagno ottiene elemento di tipo1 e la immette al Pokémon di tipo 1.

Al secondo stagno ottiene l'oggetto di tipo 2 e lo alimenta ai Pokemon di tipo 2.

Al terzo stagno ottiene l'oggetto di tipo 3, ma il Pokemon è di tipo 4. Quindi, lui deve portare con sé un alimento di tipo 4.

Al Fourth Pond ottiene l'oggetto di tipo 4. Ha già un oggetto di tipo 3 e lo alimenta ai Pokemon.

Al quinto Stagno ottiene elementi di tipo 2. Ha già un elemento di tipo 4 e la immette al Pokémon in questo stagno

class TestClass { 
public static void main(String args[]) throws Exception { 

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

    int T = Integer.parseInt(br.readLine()); 
    if(T<=10 && T>=1) { 
    for (int i = 0; i < T; i++) { 
     int count=0; 
     int numOfPonds = Integer.parseInt(br.readLine()); 
     if(numOfPonds<=100000 && numOfPonds>=1){ 
     String[] str ; 
     Map m = new HashMap(); 
     //List l = new ArrayList(); 

     for(int j=0 ; j< numOfPonds ;j++) 
       { 
        str = br.readLine().split(" "); 
        int foodType = Integer.parseInt(str[0]); 
        int PokeType = Integer.parseInt(str[1]); 
        if(foodType<=1000000 && PokeType<=1000000 && foodType>=1 && PokeType>=1 && foodType != PokeType){ 

         m.put(j,foodType); 

        //l.add(foodType); 

         //if(!(l.contains(PokeType))) 
        if(!(m.containsValue(PokeType)))       
            count++; 

        //else if(l.contains(PokeType)) 
        else if(m.containsValue(PokeType)) 
         { 
          m.values().remove(PokeType); 
          // l.remove(Integer.valueOf(PokeType)); 
          } 

        } 
       } 
     } 
     System.out.println(count); 
     } 
    } 
    } 
} 

Answer 1

seguito è il codice che ha superato tutti i test entro il tempo limite.

Come menzionato da Codebender e JimN, ho implementato containsKey() metodo che ha dimostrato di essere più veloce di containsValue().

Inoltre, per duplicati, incrementato e modificato i valori in Mappa.

class TestClass { 
public static void main(String args[]) throws Exception { 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

int T = Integer.parseInt(br.readLine()); 
if(T<=10 && T>=1) { 
for (int i = 0; i < T; i++) { 
    int count=0; 
    int numOfPonds = Integer.parseInt(br.readLine()); 
    if(numOfPonds<=100000 && numOfPonds>=1){ 
    String[] str ; 

Map<Integer,Integer> map = new HashMap<Integer,Integer>(); 
    for(int j=0 ; j< numOfPonds ;j++) 
      { 
       str = br.readLine().split(" "); 
       int foodType = Integer.parseInt(str[0]); 
       int PokeType = Integer.parseInt(str[1]); 

       if(foodType<=1000000 && PokeType<=1000000 && foodType>=1 && PokeType>=1 && foodType != PokeType){ 

       if(map.containsKey(foodType)) 
       { 
        int x = map.get(Integer.valueOf(foodType)); 
        x++; 
        map.put(foodType,x); 
       } 
       else 
       { map.put(foodType,1); 
       } 

       if(!(map.containsKey(PokeType)))       
           count++; 

       else 
        { int x = map.get(Integer.valueOf(PokeType)); 
         x--; 

         if(x==0) 
         map.remove(PokeType); 

         else 
         map.put(PokeType,x); 

         } 

       } 
      } 
    } 
    System.out.println(count); 
    } 
} 
} 
} 

Answer 2

Non so pienamente ciò che si sta cercando di fare altro che guardando il tuo codice. Ma questo ti darà la risposta più rapida. Per quanto riguarda il rilevamento del valore in HashSet, sarà O (1).

Prova questa sotto

import java.io.BufferedReader; 
import java.io.InputStreamReader; 
import java.util.HashSet; 
import java.util.Set; 

public class SalesTracking { 
public static void main(String args[]) throws Exception { 

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

    int T = Integer.parseInt(br.readLine()); 
    if(T<=10 && T>=1) { 
    for (int i = 0; i < T; i++) { 
     int count=0; 
     int numOfPonds = Integer.parseInt(br.readLine()); 
     if(numOfPonds<=100000 && numOfPonds>=1){ 
     String[] str ; 
     //Map m = new HashMap(); 
     Set m = new HashSet(); 
     for(int j=0 ; j< numOfPonds ;j++) 
       { 
        str = br.readLine().split(" "); 
        int foodType = Integer.parseInt(str[0]); 
        int PokeType = Integer.parseInt(str[1]); 
        if(foodType<=1000000 && PokeType<=1000000 && foodType>=1 && PokeType>=1 && foodType != PokeType){ 
         m.add(foodType); 
        if(!(m.contains(PokeType)))       
            count++; 
        else if(m.contains(PokeType)) 
         { m.remove(PokeType); 

         } 

        } 
       } 
     } 
     System.out.println(count); 
     } 
    } 
    } 
}