modi per accelerare il conteggio completo Ordina

Question

Ho riscontrato una domanda su hackerrank. https://www.hackerrank.com/challenges/countingsort4

Il mio primo tentativo ha superato tutti i casi di test tranne l'ultimo, a causa del timeout. Dopo aver fallito con un algoritmo più efficiente, ho migliorato il codice usando StringBuilder invece di concatenare direttamente le stringhe. Ciò ha portato il tempo di esecuzione da più di 5 secondi a 3,5 secondi.

La mia domanda è che c'è un altro modo in cui posso migliorare il tempo di esecuzione? Grazie.

Quanto segue è il mio codice.

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

Si dovrebbe provare un semplice lettore bufferizzato anziché Scanner. Lo scanner è sorprendentemente lento e ho partecipato a gare di programmazione in cui Scanner è stata l'unica ragione per cui "il limite di tempo è stato superato".

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