Geek asks and answers

Unable to run this java code

I participate in the judge’s online page, where I solved the problem, but I just can’t start my program on time. The code is as follows:

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);

I came to the conclusion that for a test case of 2 million elements (numStr = "1,000,000 1,000,000"), I got it to run up to 1.5 s, but apparently this is not enough for test cases (this says 3000 ms). And now I don’t know how I can do it faster, any help is much appreciated!

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

+3
source share
3 answers

" " - : , , , , . , .

+7

, 1000000 0; , , , , 0. , , , ( , ).

, , 0 ; , 0 1000000 0, . , , .

+1

Since the data is sorted, it is well suited for merging.

ie Logic for processing -

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
}

Only one pass passes through the file and no search is performed. Binary search may be faster in some cases.

A large buffer specification on a BufferedReader may also be required.

+1
source

More articles:


All Articles