I encountered a question on hackerrank. https://www.hackerrank.com/challenges/countingsort4
My first attempt passed all the test cases except the last one, due to timeout. After failed to come up with a more efficient algorithm, I improved the code by using StringBuilder instead of concatenating Strings directly. This brought the running time from more than 5 sec to 3.5 sec.
My question is that is there any other way that I can improve the running time? Thanks.
The following is my code.
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());
}
}
You should try a plain buffered reader instead of Scanner. Scanner is surprisingly slow and I have participated in programming competitions where Scanner was the sole reason for "time limit exceeded".
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());
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With