图解LeetCode——189. 轮转数组

一、题目

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

二、示例

2.1> 示例 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.2> 示例 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

三、解题思路

3.1> 数组拷贝方式

根据题目描述，我们需要根据给定的k的值去轮转数组，如果我们将数组nums看做是一个无限长的数组的话，其实这种轮转操作，就相当于每个nums数组中的元素都向右移动了k个位置。但是由于nums的数组长度是有限的，所以被移动越界的数组就会被移动到原数组的头部位置。根据这个规则，我们假设nums = [1,2,3,4,5,6,7], k = 3，通过每个元素的移动，来找移动的规律：

【index=0】数字1移动到index=3的位置 【index=1】数字2移动到index=4的位置 【index=2】数字3移动到index=5的位置 【index=3】数字4移动到index=6的位置 【index=4】数字5移动到index=0的位置 【index=5】数字6移动到index=1的位置 【index=6】数字7移动到index=2的位置

通过上面的移动方式，我们可以找到如下规律，即：result[(i + k) % nums.length] = nums[i];

3.2> 翻转数组

通过上面解法，我们发现必须要创建一个同等长的数组result，然后按位映射进行元素的复制操作。这样的空间复杂度就会比较高。有没有一种方式，可以在原数组基础上进行操作呢？

我们可以先将原数组nums进行翻转操作，即：将nums = [1,2,3,4,5,6,7],翻转为nums = [7,6,5,4,3,2,1],然后再按照k值进行“切分”操作，并对“切分”后的前后两部分数组再分别执行翻转操作。那么执行完毕后就是最终的结果啦。具体操作，请见下图所示：

四、代码实现

4.1> 数组拷贝方式

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++)
            result[(i + k) % n] = nums[i];
        System.arraycopy(result, 0, nums, 0, n);
    }
}

4.2> 翻转数组

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length, nk = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, nk - 1);
        reverse(nums, nk, n - 1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」