3

我参加了一个在线评委页面，在那里我解决了一个问题，但我无法让我的程序及时运行。代码如下：

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

4

3 回答 3

7

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

于 2012-05-19T01:27:28.207 回答
1

假设第一行输入是1000000 0; 您的程序将读取数百万个值并将它们输入到散列中，只是没有要查找的值，因此输出保证为 0。这显然会花费比必要更长的时间（您需要阅读它们，但是不要将它们存储在哈希中）。

此外，您只需检查第一个值为 0 即可终止；按照规范，0 1000000应该产生 0 的输出，但你的程序会终止。也许法官没有对此进行检查，但这样做是合法的。

于 2012-05-19T01:46:08.743 回答
1

由于数据已排序，因此非常适合 Merge 处理

即处理的逻辑是

Read Jacks records into array

While (More of jacks record to process)
  and (More of Jills record to process)  {

      if ( jacks_Record < Jills_Record)
         Jacks_Array_Index += 1;
      else if ( jacks_Record > Jills_Record)
         Read the next Jills_Record from the file
      else
         Match processing
}

只有一次通过文件，没有搜索。在某些情况下，二分搜索可能会更快

此外，可能值得在 BufferedReader 上指定一个大缓冲区

于 2012-05-19T02:27:30.267 回答