c++日常练习（18）-----轮转数组

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

输入: 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]

输入：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）%n 的位置，最后将新数组拷贝至原数组即可。

2、环状替换

从第一个数组开始，定义临时变量temp，使其数据与对应位置交换，并再次查询对应位置，进行交换。当数据重回下标0时，完成一圈的数据交换，但是有的数据可能并没有别触碰到，因此，从下标1开始，再次进行数据交换。

数据交换的次数为：

设一次交换数据一共循环了a圈，则一共经历了a*n个数据（其中有的没有触碰），设一共交换了b个元素，每个元素移动k个位置，则an=bk；因为an第一次就停下，所以an为b、k、的最小公倍数，则b=an/k;一共n个元素，则循环x=n/b=k/a次；即x为n、k的最大公约数

3、数组翻转

第一步：反转整个数组

第二步：找到下标k，使其分为两个数组，[0,k]、[k+1,n].

第三步：依次反转两个数组。

 1、时间复杂度O(n),空间复杂度O（n）

class Solution {
public:
    void rotate(vector& nums, int k) {
        int num=0,n=nums.size();
        vectorit(n);
        for(int i=0;i

class Solution {
public:
    void rotate(vector& nums, int k) {
int n=nums.size();
     k=k%n;//一圈调换后的数据剩余量
     int count=gcd(k, n);
     for(int i=0;i

class Solution {
public:
    void reverse(vector& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }

    void rotate(vector& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};