プログラミング スキルを練習して向上させるためだけに、InterviewStreet で質問を解くことにしました。シンプルな InsertionSort を使用して開始することにしました (シンプルだと思っていました)。 https://www.interviewstreet.com/challenges/dashboard/#problem/4e90477dbd22b 正解を得ることができました。ただし、ランタイムが問題です。テスト ケースの最大許容実行時間は 5 秒です。しかし、私は少し船外に出ています。いくつかのトリックを使用しました (コードから何かを削除する、str.length() の結果を保存するなど)。しかし、私はまだ少し船外です。
10 個のテスト ケースの現在の実行時間は次のとおりです。
1 合格 成功 0.160537
2 合格 成功 0.182606
3 合格 成功 0.172744
4 合格 成功 0.186676
5 失敗 時間制限を超えました。5.19279
6 失敗 時間制限を超えました。5.16129
7 合格 成功 2.91226
8 失敗 時間制限を超えました。5.14609
9 失敗 時間制限を超えました。5.14648
10 失敗 時間制限を超えました。5.16734
テストケースが何であるかわかりません。ランタイムの改善にご協力ください。ありがとうございました。
import java.util.Scanner;
import java.io.*;
//import java.io.BufferedWriter;
//import java.io.FileInputStream;
//import java.io.FileOutputStream;
public class Solution {
public static int[] A=new int[100001];
public static int swap=0;
public static void InsertionSort(int n){
for (int i=1; i<=n; i++){
for (int var=i; var>0; var--){
if (A[var]<A[var-1]){
int temp=A[var-1];
A[var-1]=A[var];
A[var]=temp;
swap++;
}
else {
break;
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int number_of_cases =Integer.parseInt(str);
int counter;
int [] spacearray = new int[100000];
for (int j=0; j<number_of_cases; j++){
swap=0;
str = br.readLine();
int arraylength = Integer.parseInt(str);
str = br.readLine();
counter=0;
int strlen=str.length();
for (int i=0; i<strlen-1; i++){
if (str.charAt(i) == ' '){
spacearray[counter]=i;
counter++;
}
}
spacearray[counter]=strlen;
A[0]=Integer.parseInt(str.substring(0, spacearray[0]));
for (int i=1; i<=arraylength-1; i++){
A[i] = Integer.parseInt(str.substring(spacearray[i-1]+1,spacearray[i]));
}
InsertionSort(arraylength-1);
System.out.println(swap);
}
}
}