提高反转数组的性能

Question

我正在尝试解决 Reverse Game 的问题当我提交我的代码时，在某些测试用例中它会超时。我认为问题可能出在 reverseSubArray() 方法中，但我不确定如何在这里提高性能。以下是我的代码：

    public class ReverseGame
{
    public static void main(String[] args)
    {
    Scanner scanner = new Scanner(System.in);
    int testCases = Integer.parseInt(scanner.nextLine());
    int[] numberOFBalls = new int[testCases];
    int[] ballNumberArray = new int[testCases];

    for (int i = 0; i < testCases; i++)
    {
        numberOFBalls[i] = scanner.nextInt();
        ballNumberArray[i] = scanner.nextInt();
    }

    for (int i = 0; i < testCases; i++)
    {
        process(numberOFBalls[i], ballNumberArray[i]);
    }
    scanner.close();
    }

    private static void process(int totalNumberOFBalls, int ballNumber)
    {
    int[] ballsArray = new int[totalNumberOFBalls];
    int maximumNumberOnBall = totalNumberOFBalls - 1; // This is because
                              // balls are numbered
                              // from 0.
    // As the first step is to reverse the Balls arrangement, So insert into
    // ballsArray in descending order of index.
    for (int i = 0; i < totalNumberOFBalls; i++)
        ballsArray[i] = maximumNumberOnBall--;

    for (int i = 1; i < totalNumberOFBalls; i++)
    {
        ballsArray = reverseSubArray(ballsArray, i);
    }

    int position = findPosition(ballsArray, ballNumber);
    System.out.println(position);
    }

    private static int[] reverseSubArray(int[] a, int fromIndex)
    {
    int temp = 0, counter = 1;
    int midIndex = (a.length - fromIndex) / 2;
    for (int i = fromIndex; i < fromIndex + midIndex; i++)
    {
        temp = a[a.length - (counter)];
        a[a.length - (counter)] = a[i];
        a[i] = temp;
        counter++;
    }

    /*
     * System.out.println(); for (int i = 0; i < a.length; i++)
     * System.out.print(a[i] + " ");
     */
    return a;
    }


    private static int findPosition(int[] ballsArray, int ballNumber)
    {
    for (int i = 0; i < ballsArray.length; i++)
    {
        if (ballsArray[i] == ballNumber)
        return i;
    }
    return 0;
    }

}

Answer 1

您的解决方案的时间复杂度为 O(n ^ 2)。 n = 10 ^ 5 太慢了。所以你需要使用更好的算法。这是简单的线性解决方案，它利用了我们不需要知道所有球的位置这一事实（我们只需要 k-th）：

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int testsCount = in.nextInt();
        for (int t = 0; t < testsCount; t++) {
            int n = in.nextInt();
            int k = in.nextInt();
            // Simulates all rotations,
            // but keeps track only of the k-th ball.
            // It does not matter what happens to the others.
            for (int i = 0; i < n; i++) 
                if (k >= i)
                    k = i + n - 1 - k;
            out.println(k);
        }
        out.flush();
    }
}

此解决方案的时间复杂度为 O(n)，可轻松通过所有测试用例。在线性时间内找到所有小球的位置其实是可以的，但这里不需要。

提高反转数组的性能

Improve performance of reversing array

java

arrays

algorithm

optimization

performance