题目描述

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例1：

输入: [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]

示例2：

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

方法一：直接移动元素到正确位置

这个方法需要O(n)的额外空间。

public void rotate(int[] nums, int k) {
        int[] copynum = nums.clone();
        for(int i=0;i<nums.length;i++)
            nums[(i+k)%nums.length]=copynum[i];
    }

运行时间1ms。

方法二：每次右移一个元素

public void rotate(int[] nums, int k) {
        while(k-->0) {
            int temp = nums[nums.length-1];
            for(int i=nums.length-1;i>=1;--i)
                nums[i] = nums[i-1];
            nums[0]=temp;
        }
    }

运行时间124ms。

方法三：倒置法

将一个数组循环右移可进行以下操作得到：
1.将整个数组逆置。
2.将前k个数字逆置。
3.将剩下的数字逆置。
其中逆置可转化为对称交换操作。

 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 low,int high) {
        while(low<high) {
            int temp = nums[high];
            nums[high] = nums[low];
            nums[low] = temp;
            ++low;
            --high;
        }
}

运行时间1ms。

方法四：环状替换

image.png

ublic void rotate(int[] nums, int k) {
        int a = nums[0];
        for(int pos=0,i=0;i<nums.length;i++)
        {
            pos = (pos+k)%nums.length;   //最终位置
            int temp = nums[pos];  //被替换的数
            nums[pos] = a;
            a = temp;
        }
    }     

运行时间1ms。