189 轮转数组

原题链接

轮转数组

问题描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例

示例 1

输入:

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]

示例 2

输入:

nums = [-1,-100,3,99], k = 2

输出:

[3,99,-1,-100]

解释:

• 向右轮转 1 步: [99,-1,-100,3]
• 向右轮转 2 步: [3,99,-1,-100]

提示

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

进阶

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

思路

1. 开辟额外数组空间,复制原数组，再将新数组中的元素放置到原数组下标+k的位置，超出长度从头开始计算。
2. 环状替换，把第n个元素替换到n + k mod nums.length的位置，再将原来（n + k） mod nums.length替换到 （n + k + k）mod nums.length的位置，持续循环。每次替换完回到最初的n时，需要手动将n + 1(通过循环实现)，直到已替换的长度length == nums.length。
3. 数组翻转，先翻转整个数组，再翻转[0,k-1]和[k, nums.length -1]，k = nums.length % k。

代码实现

1. 开辟额外数组空间

public void rotate(int[] nums, int k) {
    int[] arr = Arrays.copyOf(nums, nums.length);
    for (int i = 0 ; i< arr.length;i++){
        int index = i + k >= nums.length? (i + k) % nums.length : i + k;
        nums[index] = arr[i];
    }
}

2. 环状替换

public void rotate(int[] nums, int k) {
    int length = 0;
    for (int startLeft = 0; length < nums.length; startLeft++){
        int left = startLeft;
        int right = (left + k) % nums.length;
        int tmp1 = nums[left];
        int tmp2 = nums[right];
        do {
            nums[right] = tmp1;
            tmp1=tmp2;
            left = right;
            right = (left + k) % nums.length;
            tmp2 = nums[right];
            length ++;
        }while(left != startLeft);
    }
}

3. 数组反转

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

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