轮转数组三种解决方法

80 阅读 0 评论 53 点赞

我是靠谱客的博主碧蓝火，最近开发中收集的这篇文章主要介绍轮转数组三种解决方法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给你一个数组，将数组中的元素向右轮转 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 <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

讨论归纳一：辅助数组，划分旋转区域

第一步：根据数组长度 N 和跨步 K 计算出需要转移至数组头部的元素个数
第二步：将数组划分为两个区域
   注意：（逻辑区域，思想区域，这里是为了方便理解，不需要真实状态标注）
   区域一：需要旋转到右边的数（头部需要旋转到尾部的元素）
   区域二：需要旋转到左边的数（尾部需要旋转到头部的元素）
第三步：迁移数据到辅助数组
   先迁移区域二，在迁移区域一
第四步：拷贝回原数组

示例一：辅助数组，划分旋转区域

public void rotate(int[] nums, int k) {

    // 计算尾部需要移至头部元素个数
    k %= nums.length;

    int N = nums.length;
    int j = 0;
    int[] help = new int[nums.length];

    // 归位区域二
    // 即归位需要移至头部的元素
    for (int i = N - k; i < N; i++) {
        help[j++] = nums[i];
    }

    // 归位区域一
    // 即归位需要移至尾部的元素
    for (int i = 0; i < N - k; i++) {
        help[j++] = nums[i];
    }

    System.arraycopy(help, 0, nums, 0, N);
}

复杂度分析
时间复杂度：O(n)。遍历数组需要 O(n) 的时间。
空间复杂度：O(n)。需要辅助数组。

讨论归纳二：辅助数组，前世今生

重点：数组元素 a[i] 通过潘多拉魔盒找到今生（a[i] 旋转后在新的位置下标 j）

遍历数组，找到前世 a[i] 的今生 j, 并安排到辅助数组对应的位置

魔盒：j = (i+k) % N
示例二：辅助数组，前世今生
public void rotate(int[] nums, int k) {
    int n = nums.length;
    int[] help = new int[n];
    for (int i = 0; i < n; ++i) {
        // 旋转 k, 相当于 nums[i] 元素向后跨步 k 个下标
        // nums 数组下标范围是 [0, N-1]
        // 跨步后下标超过N-1，从 0 继续跨步
        // 计算 nums[i] 旋转后在辅助数组中的相对位置
        int m = (i + k) % n;
        help[m] = nums[i];
    }
    System.arraycopy(help, 0, nums, 0, n);
}

复杂度分析
时间复杂度：O(n)。其中 n 为数组的长度。
空间复杂度：O(n)。需要额外空间。

讨论归纳三：翻转数组
归纳一中，划分了旋转区域，利用辅助数组实现区域旋转，实现了数组旋转的目的。

实际上，我们不需要借助辅助数组也能实现区域旋转，达到交换目的。

首先还是利用模运算计算出需要转移到数组头部的元素个数。

在通过翻转数组实现旋转。
1 2 3 4 5 6 7 K=3

第一步：根据数组长度 N 和跨步 K 计算出需要转移至数组头部的元素个数
第二步：将数组划分为两个区域
   注意：（逻辑区域，思想区域，这里是为了方便理解，不需要真实状态标注）
   区域一：需要旋转到右边的数（头部需要旋转到尾部的元素）
   1 2 3 4

   区域二：需要旋转到左边的数（尾部需要旋转到头部的元素）
   5 6 7

第三步：翻转整个数组
   7 6 5 4 3 2 1
第四部：翻转区域二，在翻转区域一
   翻转区域二 5 6 7
   翻转区域一 1 2 3 4


示例三：翻转数组
public void rotate(int[] nums, int k) {

    // 计算尾部需要移至头部元素个数
    k %= nums.length;

    // 翻转数组所有元素
    reverse(nums, 0, nums.length - 1);
    // 翻转已经移至头部的元素
    reverse(nums, 0, k - 1);
    // 翻转已经移至尾部的元素
    reverse(nums, k, nums.length - 1);
}

// 翻转 [start, end] 范围内的数
public void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start += 1;
        end -= 1;
    }
}