Cấu trúc dữ liệu cho hoạt động chứa() nhanh hơn?

Question

Trong vấn đề, tôi phân tích cú pháp đầu vào (số nguyên) và kiểm tra đồng thời nếu nó tồn tại trong cấu trúc dữ liệu, nếu không thì hãy thêm nó vào.

Input là - 2 số nguyên cách nhau bởi không gian của kích thước> = 1 và < = 1000000

tôi đã cố gắng sử dụng HashMap, TreeMap (put() và containsValue() phương pháp) - nhưng có vẻ như họ đang dùng quá nhiều thời gian. (5 trong số 10 trường hợp thử nghiệm đang vượt quá thời hạn)

Khi sử dụng ArrayList (thêm() và chứa() phương pháp) - (4 trong số 10 trường hợp thử nghiệm vượt quá thời hạn)

Các hoạt động này là để được thực hiện trong vòng 2 cho vòng lặp, bên trong một điều kiện nếu.

lặp có thể thay đổi như sau: -

1 vòng lặp for - 1-10

2 vòng lặp for - 1-100.000

vì vậy tôi đoán cho lặp bậc cao trong vòng 2 nó vượt quá thời gian giới hạn.

Có cách nào khác để tôi có thể thực hiện tác vụ này trong thời gian ngắn hơn không.

Vấn đề:

Một Monk gặp N ao và ở mỗi ao một fooditem (input 1) và một pokemon (đầu vào 2) được tìm thấy.

Nhà sư có thể cấp vật phẩm tại ao i'th cho Pokemon ở ao nếu loại khớp. Nhà sư có thể phải mang theo một số đồ ăn với anh ta trước khi rời đi để nuôi tất cả các Pokemon. Giúp anh ta tìm số vật phẩm anh ta phải mang theo, để có thể đi qua vùng đất an toàn.

Giải thích

Tại Đầu tiên Pond anh nhận được item của type1 và thức ăn nó vào Pokemon của type1.

Tại Second Pond, anh ấy nhận được mục thuộc loại 2 và cấp dữ liệu cho Pokemon type2.

Tại Ao thứ ba, anh ấy nhận được vật phẩm thuộc loại 3, nhưng Pokemon thuộc loại4. Do đó, ông phải mang theo một loại thực phẩm thuộc loại 4 với anh ta.

Tại Ao thứ tư, anh ta nhận được vật phẩm loại 4. Anh ta đã có một vật phẩm thuộc loại 3 và cấp nó cho Pokemon.

Tại Fifth Pond anh nhận được mặt hàng loại 2. Ông đã có một mục loại 4 và thức ăn nó vào Pokemon ở ao này

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

Tiếp theo là mã mà thông qua tất cả các trường hợp thử nghiệm trong thời gian giới hạn.

Như đã đề cập bởi Codebender và JimN, tôi thực hiện containsKey() phương pháp đó được chứng minh là nhanh hơn so với containsValue().

Ngoài ra, đối với các bản sao, tăng lên và thay đổi các giá trị trong Bản đồ.

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

Đừng hoàn toàn biết những gì bạn đang cố gắng làm khác hơn nhìn vào mã của bạn. Nhưng điều này sẽ cung cấp cho bạn phản ứng nhanh nhất. Theo như tìm kiếm giá trị trong HashSet đi nó sẽ là O (1).

Hãy thử điều này bên dưới

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