无法让这个java代码运行得更快

Question

我正在参与一个在线评判页面,在那里我解决了一个问题,但我无法让我的程序及时运行.代码如下:

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
Set l = new HashSet();
String line;
String[] numStr;
 while(true){
  line = in.readLine();      
  numStr = line.split("\\s");      
  int a = Integer.parseInt(numStr[0]);
  if(a == 0){
     System.exit(0);
  }
  int n = 0;
  int b = Integer.parseInt(numStr[1]);
  l.clear();
  for(int i=0;i<a;i++){
    l.add(in.readLine());
  }
  for(int i=0;i<b;i++){
    if(l.contains(in.readLine())){
      n++;
    }
  }
  System.out.println(n);

我找到了一个200万项测试用例(numStr ="1000000 1000000"),我让它在1.5秒以下运行,但显然这对于​​测试用例来说还不够(它说3000ms).现在我不知道怎样才能让它更快,任何帮助都非常感谢!

问题:http://coj.uci.cu/24h/problem.xhtml？abb = 1438

Answer 1

输入规范的"递增顺序"部分是关键:由于两个列表都是预先排序的,您可以将第一个列表读入数组,然后使用二进制搜索从最后一个项目的位置到结束数组来决定你是否有匹配.实际上,即使是第一个数组的线性搜索也可能有效,因为您最多需要遍历一次.