189. 轮转数组#

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

1
示例 1:
2

3
输入: nums = [1,2,3,4,5,6,7], k = 3
4
输出: [5,6,7,1,2,3,4]
5
解释:
6
向右轮转 1 步: [7,1,2,3,4,5,6]
7
向右轮转 2 步: [6,7,1,2,3,4,5]
8
向右轮转 3 步: [5,6,7,1,2,3,4]
9
示例 2:
10

11
输入：nums = [-1,-100,3,99], k = 2
12
输出：[3,99,-1,-100]
13
解释:
14
向右轮转 1 步: [99,-1,-100,3]
15
向右轮转 2 步: [3,99,-1,-100]

题解#

先对轮转步数k求余。real_step = k % nums.size()，防止k大于数组长度nums.size()

额外数组，暴力#

创建一个长度为real_step的数组存储后面的元素。拷贝。
将前面的元素移动real_step步，到数组末尾。
将临时数组中的元素，拷贝回去。

1
class Solution {
2
public:
3
    void rotate(vector<int>& nums, int k) {
4
        int n = nums.size();
5
        int real_step = k % n;
6
        vector<int> tmp_vec(real_step);
7
        // 拷贝后面元素
8
        for(int i = 0; i < real_step; i++){
9
            tmp_vec[i] = nums[n - real_step + i];
10
        }
11

12
        // 移动数组
13
        for(int i = n - real_step - 1; i >= 0; i--){
14
            nums[i + real_step] = nums[i];
15
        }
16

17
        // 放到前面
18
        for(int i = 0; i < real_step; i++){
19
            nums[i] = tmp_vec[i];
20
        }
21
    }
22
};