☆打卡算法☆LeetCode 188. 轮转数组 算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个数组，将数组中的元素向右轮转k个位置。”

题目链接：

来源：力扣（LeetCode）

链接： 189. 轮转数组 - 力扣（LeetCode）

2、题目描述

给你一个数组，将数组中的元素向右轮转 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、思路分析

这道题题意是要求我们轮转数组，返回轮转后的数组。

这道题可以使用一个新数组用来存放每个元素到正确的位置，用n表示数组的长度，遍历数组，将数组下标为i的元素放到新数组下标为i+k的位置。

最后将新数组拷贝至原数组即可。

2、代码实现

代码参考：

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

3、时间复杂度

时间复杂度：O(n)

其中n数数组的长度。

空间复杂度：O(n)

其中n数数组的长度。

三、总结

这道题使用新数组的原因在于如果直接将每个元素放到它要到达的位置的话。

被放置的位置的元素会被覆盖而丢失。

那么，也可以利用这点，使用一个临时变量，将临时变量保存数组i的值。

此时找到i位置的值需要到达位置k，然后将temp=nums[k]，完成位置k的数值更新。

根据上面的规则继续找到下一个位置x，也就是temp=nums[x+k]，从而完成下一个位置的更新。

不断重复上述过程，直到回到初始位置。

这样就避免了使用额外数组。