更快的 contains() 操作的数据结构？

Question

在问题中，我解析输入（整数）并同时检查它是否存在于数据结构中，如果不存在则添加它。

输入是 - 由 space 分隔的 2 个整数，大小 >=1 且 <= 1000000

我尝试使用 HashMap 、 TreeMap （put() 和 containsValue() 方法）- 但它们似乎花费了太多时间。（10 个测试用例中有 5 个超过时间限制）

使用ArrayList时（add()和contains()方法）-（10个测试用例中有4个超过时间限制）

这些操作将在第二个 for 循环内执行，在 if 条件内。

迭代可能变化如下：-

第一个 for 循环 - 1 到 10

第二个 for 循环 - 1 到 100000

所以我猜想在第二个循环中进行高阶迭代会超过时间限制。

有没有其他方法可以让我在更短的时间内完成这项任务。

问题：

一个僧侣遇到 N 个池塘，在每个池塘找到一个食物（输入 1）和一个口袋妖怪（输入 2）。

如果类型匹配，僧侣可以将第 i 个池塘中的物品喂给池塘中的神奇宝贝。和尚在离开之前可能需要随身携带一些食物，以喂养所有的神奇宝贝。帮他算出他必须携带的物品数量，才能安全通过这片土地。

说明

在第一个池塘，他得到了类型 1 的物品并将其喂给类型 1 的神奇宝贝。

在第二个池塘他得到类型 2 的物品并将其喂给类型 2 的神奇宝贝。

在第三个池塘他得到了类型 3 的物品，但是口袋妖怪是类型 4 。因此，他必须随身携带4类食物。

在 Fourth Pond 他得到了类型 4 的物品。他已经有了一个类型 3 的物品并将其喂给神奇宝贝。

在第五池他得到了类型 2 的物品。他已经有了一个类型 4 的物品并把它喂给了这个池塘的口袋妖怪

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

除了查看您的代码外，不完全知道您要做什么。但这会给你最快的反应。就在 HashSet 中找到值而言，它将是 O(1) 。

试试下面这个

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

Answer 2

以下是在限定时间内通过所有测试用例的代码。

正如 Codebender 和 JimN 所提到的，我实施了 containsKey() 方法，事实证明它比 containsValue().

此外，对于重复项，增加并更改了 Map 中的值。

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

更快的 contains() 操作的数据结构？

Data Structure for faster contains() operation?

java

contains

time-complexity

data-structures