java - Collections.rotate 方法不适用于大型整数数组

Question

我试图为 HackerRank 问题“数组:左旋转”找到更优化的解决方案，因此我将 int 基元数组转换为整数数组并使用方法 Collections.rotate。在第一行，用户输入n = 整数个数，则 k = 左转数并且在第二行，用户输入 n 个以空格分隔的整数。

但是当使用以下输入进行测试时:

61 48
431 397 149 275 556 362 852 789 601 357 516 575 670 507 127 888 284 405 806 27 495 879 976 467 342 356 908 750 769 947 425 643 754 396 653 595 108 75 347 394 935 252 683 966 553 724 629 567 93 494 693 965 328 187 728 389 70 288 509 252 449

结果与预期不同。我的代码如下:

public class HackerRankArraysLeftRotationOptimized {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // the number of integers
        int k = in.nextInt(); // the number of left rotations you must perform
        int a[] = new int[n];
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
        }
        
        Integer[] newArray = new Integer[a.length];
        int i = 0;
        for (int value: a) {
            newArray[i++] = Integer.valueOf(value);
        }
        
        for (int j = 0; j < k; j++) {
            Collections.rotate(Arrays.asList(newArray), k);
        }
        
         for (int m = 0; m < newArray.length; m++) {
            System.out.print(newArray[m] + " ");
        }
        
    }
    
}

有人可以向我解释 Collections.rotate 方法有什么问题吗？

Answer 1

Collections.rotate() 向右旋转，这是第一个问题。第二个问题是你在一个循环中旋转 k，所以你要计算 k*k 次。你只需要这样做(而不是在循环中):

Collections.rotate(Arrays.asList(newArray), -k);