LeetCode旋转数组（Rotate Array）问题：两种思路及代码错误排查

问题描述 #

给定整数数组nums，将数组向右旋转k个位置（k为非负整数）。

第一种思路的问题排查 #

你的第一种思路是：创建长度为原数组+1的新数组，将原数组元素从新数组索引1开始存入（如原数组{1,2,3,4}变为{无效值,1,2,3,4}），交换新数组最后一位到首位后，将有效部分复制回原数组，重复k次。这里的常见错误包括：

• 效率瓶颈：每次旋转都要创建新数组并遍历复制，时间复杂度为O(k*n)，当k远大于数组长度n时（比如k=10^9），会直接超时。实际上旋转n次后数组会回到原状态，必须先计算k = k % n，砍掉不必要的循环。
• 元素复制范围错误：处理后的新数组，有效元素范围容易取错。比如原数组长度为n，新数组长度为n+1，将最后一位移到首位后，应该取新数组前n个元素（索引0到n-1）复制回原数组，否则会引入无效值或丢失元素。
• 数组越界风险：如果代码中对新数组的索引操作没控制好，比如误访问n+1位置，会触发数组越界异常。

第二种思路的优化点 #

第二种思路：暂存数组最后一个元素，将数组元素从i移到i+1后把暂存元素放到首位。这个思路逻辑是对的，但同样存在效率问题：每次旋转都要遍历数组一次，k次旋转的时间复杂度还是O(k*n)，对大k值不友好。同样需要先做k = k % n的优化。

最优解法推荐 #

三次反转法（O(n)时间，O(1)空间） #

通过三次反转操作实现原地旋转：

1. 反转整个数组；
2. 反转前k个元素；
3. 反转剩余的n-k个元素。

示例代码（Java）：

public void rotate(int[] nums, int k) {
    k = k % nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}

private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

一次性复制法（O(n)时间，O(n)空间） #

用额外数组直接计算每个元素的最终位置，再复制回原数组：

public void rotate(int[] nums, int k) {
    int n = nums.length;
    k = k % n;
    int[] temp = new int[n];
    for (int i = 0; i < n; i++) {
        temp[(i + k) % n] = nums[i];
    }
    System.arraycopy(temp, 0, nums, 0, n);
}

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