Улучшение характеристик реверсивного массива

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 -х):

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) времени и легко проходит все испытания случаев. Фактически можно найти положения всех шаров в линейном времени, но здесь это не требуется.