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]

以矩阵的观点

\begin{matrix} C=[A,B] \\ C^T=[B^T,A^T]\\ 目标：[B,A]=[(B^T)^T,(A^T)^T] \end{matrix}

此题用R表示翻转

\begin{matrix} C=[A,B] \ \ \ C^R=[B^R,A^R]\\ 目标：[B,A]=[(B^R)^R,(A^R)^R] \end{matrix}
操作 结果
原始数组 1 2 3 4 5 6 7
翻转所有元素 7 6 5 4 3 2 1
翻转[0,k mod n−1] 区间的元素 5 6 7 4 3 2 1
翻转 [k mod n,n−1]区间的元素 5 6 7 1 2 3 4 
class Solution {

public:

    void reverse(vector<int>& nums, int start, int end) {

        while (start < end) {

            swap(nums[start], nums[end]);

            start += 1;

            end -= 1;

        }

    }

  

    void rotate(vector<int>& nums, int k) {

        k %= nums.size();

        reverse(nums, 0, nums.size() - 1);

        reverse(nums, 0, k - 1);

        reverse(nums, k, nums.size() - 1);

    }

};