Java实现数组右移k次时ArrayOutOfBounds异常及输出错误问题求解

异常与错误原因 #

• 数组越界异常原因：当i初始值为0时，第一次执行temp = nums[i-1]会访问下标为-1的数组元素，Java数组合法下标范围是0 ~ nums.length-1，负下标直接触发ArrayOutOfBounds异常。
• i初始值改为1后结果错误原因：当前内层循环从左到右交换相邻元素的逻辑，实际效果是将数组第一个元素逐步移动到末尾，实现的是向左旋转1次，和你需要的向右旋转逻辑完全相反，因此输出结果不符合预期。

修正方案 #

基础修正（保持逐轮旋转的逻辑） #

如果保留你原本逐轮旋转的写法，调整内层循环逻辑即可：每次右旋转1位时，先暂存数组最后一个元素，再从后往前遍历将所有元素后移一位，最后将暂存的元素放到数组头部。同时可以先对k取数组长度的模，避免k大于数组长度时的无效循环。
修正后代码如下：

public void rotate(int[] nums, int k) {
    // 避免k大于数组长度时做无效旋转
    k = k % nums.length;
    if (k == 0 || nums.length <= 1) {
        return;
    }
    for (int j = 0; j < k; j++) {
        // 暂存最后一位元素
        int temp = nums[nums.length - 1];
        // 从后往前遍历，所有元素后移一位
        for (int i = nums.length - 1; i > 0; i--) {
            nums[i] = nums[i - 1];
        }
        // 暂存的元素放到头部
        nums[0] = temp;
    }
}

更优方案（三次翻转法，时间复杂度O(n)） #

如果要提升性能，可以用三次翻转的方法，避免嵌套循环：

1. 翻转整个数组
2. 翻转前k个元素
3. 翻转后nums.length - k个元素
   代码如下：

public void rotate(int[] nums, int k) {
    k = k % nums.length;
    if (k == 0 || nums.length <= 1) {
        return;
    }
    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--;
    }
}

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