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

Question

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

输入是 - 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 个池塘中的元素喂给池塘中的神奇宝贝。和尚在离开之前可能需要随身携带一些食物，以喂养所有的神奇宝贝。帮他算出他必须携带的元素数量，才能安全通过这片土地。

解释

在 First Pond，他得到 type1 的元素并将其喂给 type1 的神奇宝贝。

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

在 Third Pond 他得到了类型 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

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

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