Java整数列表左旋转代码超时性能优化方案

需求说明 #

给定输入整数列表与旋转偏移量，完成数组左旋转操作：

• 输入第一行为两个空格分隔的整数：
  • n：整数列表的元素总个数
  • d：需要对列表执行的左旋转操作次数
• 输入第二行为空格分隔的整数，构成待操作数组arr[]

约束条件 #

• 1 ≤ n ≤ 10^5
• 1 ≤ d ≤ n
• 1 ≤ arr[i] ≤ 10^6

样例 #

输入：

• n=5，d=4
• 数组元素：1 2 3 4 5

输出：
5 1 2 3 4

原有代码问题 #

现有实现逻辑符合功能要求，但大规模数据下会触发超时，原代码如下：

public static List<Integer> rotateLeft(int d, List<Integer> arr) {

    int size = arr.size();
    while(d>0) {
        int temp = arr.get(0);
        for(int i = 0; i<size; i++){
            if(i != size-1){
                arr.set(i,arr.get(i+1));
            } else {
                arr.set(i,temp);
            }
        }
        d--;
    }
    
    return arr;
}

超时根因：原实现每执行1次左旋转，就要遍历整个数组做元素移动，总共要执行d轮全数组遍历，时间复杂度为O(nd)*。当n和d都达到1e5量级时，总操作次数会达到百亿级别，远超出常规时间限制能承载的运算量，比如n=73642、d=60581的测试用例，总操作次数超过44亿，必然超时。

优化实现 #

左旋转d次的本质是把数组前d个元素整体切下来，拼接到数组尾部，完全不需要逐次做单步旋转，直接按规则构造结果即可，时间复杂度可降到O(n)，轻松通过所有测试用例。

实现1：直接构造结果（写法简单易读，推荐） #

public static List<Integer> rotateLeft(int d, List<Integer> arr) {
    int size = arr.size();
    int rotate = d % size; // 兼容d大于数组长度的场景，本题约束下可省略
    List<Integer> result = new ArrayList<>(size);
    // 先拼接从第d个位置开始到数组末尾的元素
    for (int i = rotate; i < size; i++) {
        result.add(arr.get(i));
    }
    // 再拼接前d个元素
    for (int i = 0; i < rotate; i++) {
        result.add(arr.get(i));
    }
    return result;
}

实现2：三次反转法（O(1)额外空间） #

如果要求不使用额外的结果列表空间，可以通过三次局部反转实现同样效果，时间复杂度同样为O(n)：

1. 反转数组前d个元素
2. 反转数组第d个位置到末尾的元素
3. 反转整个数组

public static List<Integer> rotateLeft(int d, List<Integer> arr) {
    int size = arr.size();
    int rotate = d % size;
    reverse(arr, 0, rotate - 1);
    reverse(arr, rotate, size - 1);
    reverse(arr, 0, size - 1);
    return arr;
}

// 反转列表指定闭区间内的元素
private static void reverse(List<Integer> arr, int left, int right) {
    while (left < right) {
        int temp = arr.get(left);
        arr.set(left, arr.get(right));
        arr.set(right, temp);
        left++;
        right--;
    }
}

内容的提问来源于stack exchange，提问作者Som