Struktura danych na szybsze zawiera() działanie?

Question

W problemie parsuję dane wejściowe (integer) i jednocześnie sprawdzam, czy istnieje w strukturze danych, jeśli nie, to dodaj.

Input - 2 liczby całkowite oddzielone spacją wielkości> = 1 i < = 1000000

Próbowałem za pomocą HashMap, TreeMap (put() i containsValue() metoda) - ale wydaje się, że biorą zbyt wiele czasu. (5 z 10 przypadków testowe przekroczenia limitu czasowego)

Przy użyciu ArrayList (add() i zawiera() metoda) - (4 z 10 przypadków testowych przekroczeniu limitu czasowego)

Operacje te są wykonać wewnątrz pętli for 2, w warunkach if.

iteracji może zmieniają się, jak następuje: -

1-ty pętli - 1 do 10

2-sze pętli - 1 do 100000

więc, że za wyższej iteracji zamówienia w 2 pętli przekracza czas limit.

Czy istnieje jakikolwiek inny sposób wykonania tego zadania w krótszym czasie.

problemu:

Mnich napotyka N stawów i w każdym stawie fooditem (wsad 1) i pokemon (wsad 2) znajduje się.

Mnich może nakarmić przedmiot przy "stawie" Pokemonowi nad stawem, jeśli ten typ pasuje. Mnich może mieć przy sobie trochę jedzenia przed wyjazdem, aby nakarmić wszystkie Pokemony. Pomóż mu znaleźć liczbę przedmiotów, które musi nosić, aby móc bezpiecznie przejść przez ziemię.

Wyjaśnienie

At First Pond dostaje przedmiot od typu 1 i podaje ją do pokemon z typu 1.

Przy drugim stawie dostaje przedmiot typu 2 i podaje go pokemonowi typu 2.

Przy Trzecim stawie dostaje przedmiot typu 3, ale Pokemon ma typ 4. Dlatego też musi przynieść ze sobą artykuł spożywczy typu 4.

Przy Czwartym stawie dostaje przedmiot typu 4. Ma już przedmiot typu 3 i podaje go Pokemonowi.

Na Piątej Staw dostaje elementy typu 2. On już ma pozycję typu 4 i podaje ją do Pokemon w tym stawie

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

Poniżej znajduje się kod, który przeszedł wszystkie przypadki testowe w terminie.

Jak wspomniano przez Codebender i JimN, I wdrożone containsKey() metodę, która okazała się szybciej niż containsValue().

Dodatkowo, dla duplikatów, inkrementowano i zmieniano wartości w Mapie.

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

nie w pełni wiedzieć, co staramy się robić inne niż patrząc na twój kod. Ale to da ci najszybszą odpowiedź. Jeśli chodzi o znalezienie wartości w HashSet, to będzie to O (1).

Spróbuj poniżej

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