java 数据结构更快的包含()操作？

hyrbngr7 于 2023-04-19 发布在 Java

关注(0)|答案(3)|浏览(154)

在这个问题中，我解析输入（整数），同时检查它是否存在于数据结构中，如果不存在，则添加它。
输入是-2个整数，由大小〉=1且〈= 1000000的空格分隔
我试过使用HashMap，TreeMap（put()和containsValue()方法）-但是看起来它们花费了太多的时间。（10个测试用例中有5个超过了时间限制）
当使用ArrayList（add（）和contains（）方法）时-（10个测试用例中有4个超过了时间限制）
这些操作将在第二个for循环中，在if条件中执行。
迭代可以如下变化：-
第1个循环- 1至10
第二个循环- 1到100000
所以我猜对于第二次循环中的高阶迭代，它超过了时间限制。
有没有其他方法可以在更短的时间内完成这项任务。

问题：

一个和尚遇到N个池塘，在每个池塘找到一个食物项目（输入1）和一个口袋妖怪（输入2）。
和尚可以在第i个池塘的项目饲料的口袋妖怪在池塘，如果类型匹配.和尚可能要携带一些食品与他离开之前，以养活所有的口袋妖怪.帮助他找到他必须携带的物品的数量，才能通过安全的土地.

说明

在第一池塘，他得到类型1的物品，并将其喂给类型1的口袋妖怪。
在第二池塘，他得到了类型2的物品，并将其喂给了类型2的口袋妖怪。
在第三池塘他得到了类型3的物品，但是口袋妖怪是类型4的。因此，他必须带着类型4的食物物品。
在第四个池塘，他得到了类型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);
      }
    }
    }
}

Java

来源：https://stackoverflow.com/questions/31331725/data-structure-for-faster-contains-operation

3条答案

按热度按时间

sxpgvts31#

以下是在时间限制内通过所有测试用例的代码。
正如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);
  }
}
}
}

赞(0）回复(0）举报 2023-04-19

bkhjykvo2#

不完全知道你在做什么，除了看你的代码。但这将给予你最快的响应。只要找到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);
      }
    }
    }
}

赞(0）回复(0）举报 2023-04-19

3zwjbxry3#

您可以使用bloom filter和Set<T>的组合。
Bloom filter是一种节省空间的概率数据结构......用于测试元素是否是集合的成员。假阳性匹配是可能的，但假阴性是不可能的-换句话说，查询返回“可能在集合中”或“肯定不在集合中”。
算法：
1.首先查询 bloom filter，如果它返回“definitely not in set”，则该元素是新的。
1.如果 bloom filter 返回“possibly in set”，则调用Set<T>.contains()以确保包含。