java - 无法让此 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 秒，但显然这对于​​测试用例来说还不够(据说是 3000 毫秒)。现在我不知道怎样才能让它更快，非常感谢任何帮助!

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

Answer 1

输入规范的“按递增顺序”部分是关键:由于两个列表都是预先排序的，您可以将第一个读入数组，然后使用二分查找从最后一项的位置到数组的末尾来决定你是否有匹配项。事实上，即使对第一个数组进行线性搜索也可能有效，因为您最多需要遍历它一次。