博客

题目：给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数

实例：

输入: nums = [1,2,3,4,5,6,7], k = 3

输出: [5,6,7,1,2,3,4]

解释:

向右轮转 1 步: [7,1,2,3,4,5,6]

向右轮转 2 步: [6,7,1,2,3,4,5]

向右轮转 3 步: [5,6,7,1,2,3,4]

解法一：新数组

解题思路：用新数组存储原数组处理结果，将新数组内容覆盖回原数组。数组长度可能小于轮转数k，取余来确定元素位置。

时间复杂度：O(n)

空间复杂度：O(n)

    @Test
    //简单解法：用一个新数组储存处理结果，将新数组覆盖至原数组
    public void rotate(int[] nums, int k) {
        int arr[] = new int[nums.length];
        for(int i = 0;i< nums.length;i++)
            arr[(i+k)%nums.length] = nums[i];
        System.arraycopy(arr,0,nums,0,nums.length);
    }

解法二：环状替换法

解题思路：元素向后轮转时，先将被覆盖元素赋值给一个临时变量temp，覆盖元素pre赋值给被覆盖元素，将temp中元素赋值给pre，让被覆盖元素作为覆盖元素继续向后覆盖。若k不是数组长度的因数，覆盖结束已经将数组完全处理好。若k为数组长度的因数，覆盖结束回到开始位置，此时只走了一圈数组，后面的元素并没有得到处理，需要从后一个元素再次启动处理。如果k取余数为0，则数组不用处理。

时间复杂度：O(n)

空间复杂度：O(1) 常数个辅助空间

public void rotate(int[] nums, int k) {
        int len = nums.length,n=len;
        int sub = 0,i = 0;
        int pre = nums[sub],temp = nums[sub];

        //数组不用处理
        if(k%len == 0) return;

        //确保n个数据都处理完
        while (n-- != 0){
            sub = (sub+k)%len;
            temp = nums[sub];
            nums[sub] = pre;
            pre = temp;
            //覆盖结束没有处理完数据时再次启动处理
            if(sub == i){
                sub = i++;
                pre = nums[sub];
                temp = nums[sub];
            }
        }
    }