sposoby przyspieszenia sortowania zliczającego

Question

Napotkałem pytanie na temat hackerranka. https://www.hackerrank.com/challenges/countingsort4

Moja pierwsza próba przeszła wszystkie przypadki testowe oprócz ostatniej z powodu przekroczenia limitu czasu. Po tym, jak nie udało mi się wymyślić bardziej wydajnego algorytmu, poprawiłem kod za pomocą StringBuilder zamiast bezpośrednio konkatenować ciągi. To przyniosło czas działania od ponad 5 sekund do 3,5 sekundy.

Moje pytanie brzmi: czy jest jakiś inny sposób na ulepszenie czasu pracy? Dzięki.

Poniżej znajduje się mój kod.

public class Solution { 

    public static void main(String[] args) { 
     Scanner scanner = new Scanner(System.in); 

     int N = scanner.nextInt(); 
     scanner.nextLine(); 

     int[] oriNum = new int[N];   
     String[] oriStr = new String[N]; 
     int[] count = new int[100]; 
     int[] indices = new int[100]; 
     int[] output = new int[N]; 

     // save the originals and the count array 
     for (int i = 0; i < N; i++) { 
      oriNum[i] = scanner.nextInt(); 
      oriStr[i] = scanner.nextLine().trim(); 
      count[oriNum[i]]++; 
     } 

     // accumulate the count array 
     indices[0] = 0; 
     for (int i = 1; i < 100; i++) { 
      indices[i] = indices[i-1] + count[i-1]; 
     } 

     // output order 
     for (int i = 0; i < N; i++) { 
      int num = oriNum[i]; 
      output[indices[num]++] = i; 
     } 

     int bar = N/2; 
     StringBuilder sb = new StringBuilder(); 
     for (int i = 0; i < N; i++) {    
      int index = output[i]; 
      if (index < bar) 
       sb.append("- "); 
      else 
       sb.append(oriStr[index]+ " "); 
     } 
     System.out.println(sb.toString()); 
    } 
} 

Answer 1

Powinieneś wypróbować zwykły buforowany czytnik zamiast skanera. Skaner jest zadziwiająco wolny i brałem udział w konkursach programistycznych, w których Scanner był jedynym powodem przekroczenia limitu czasu.

Answer 2

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 
public class Solution 
{ 
    public static void main(String[] args)throws Exception 
{ 
    BufferedReader in=new BufferedReader(new InputStreamReader(System.in)); 
    int n=Integer.parseInt(in.readLine()); 
    int[] c=new int[100]; 
    String[][] dt=new String[100][10300]; 
    for(int i=0;i<n;i++) 
    { 
     String[] str=in.readLine().split(" "); 
     int val=Integer.parseInt(str[0]); 
     if(i<n/2) 
      dt[val][c[val]]="-"; 
     else 
      dt[val][c[val]]=str[1]; 
     c[val]++; 
    } 
    StringBuilder sb=new StringBuilder(""); 
    for(int i=0;i<100;i++) 
     if(i<n) 
     for(int k=0;k<c[i];k++) 
      if(dt[i][k]!=null) 
       sb.append(dt[i][k]+" "); 
      else break; 
    System.out.println(sb.toString()); 
} 
}