0

只是为了练习和提高我的编程技能，我决定在 InterviewStreet 上解决问题。我决定开始使用简单的 InsertionSort（我希望它很简单）。 https://www.interviewstreet.com/challenges/dashboard/#problem/4e90477dbd22b 我能够得到正确的答案。但是运行时是一个问题。测试用例允许的最大运行时间为 5 秒。但是我有点过火了。我使用了一些技巧（比如从代码中删除一些东西。存储 str.lenght() 的结果等）。不过我还是有点过火了。

十个测试用例的当前运行时是：

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

2 回答 2

0

使用二叉索引树来解决这个问题

于 2013-01-16T12:59:46.923 回答
0

这里的瓶颈是插入排序算法。它的时间复杂度为 O(n^2)，n 高达 10^5，在 interviewstreet Judge 机器上很容易超过 5 秒。此外，当抛出 TLE 信号时，您的程序将停止执行。因此，到 5 的轻微开销并不是实际运行时间的指标。它是由检测 TLE 和停止执行之间的延迟引入的。

为了历史的缘故，这个问题最初是作为codeprint-1的一部分出现的。使用插入排序不是在这里进行的方法，否则问题将完全放弃。

暗示

使用所有值都在 [1,10^6] 范围内的事实。您在这里真正要做的是查找数组 A 中的反转数，即查找所有 i < j st A[i] > A[j] 对。考虑一种数据结构，它允许您以对数时间复杂度（如二叉索引树）找到每个插入操作所需的交换次数。当然，还有其他方法。

于 2013-01-16T18:24:59.883 回答