[数据结构与算法]一. 数组_数组的旋转_189. 轮转数组

题目描述
给你一个数组，将数组中的元素向右轮转 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]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-array

首先，这里看到难度是中等的，感觉还是会有难度的，但是一看题目感觉不是很难，这样就让我试试到底难不难。
取余加数法
1.首先会知道对应的k值，我们的想法是数组的长度将对应的k值取余。
2.取余的数，就是我们下标加上的长度
3.最简单的是创建一个数组，让对应的下标赋值到新创建的数组中，这样就不用考虑到原来的值被覆盖的问题

// nums.assign(newArr.begin(), newArr.end());
// 这里用这个函数可以将newArr函数的值，拷贝到nums数组中，输入的是newArr的起始地址
void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> temp(n);

    //这里创建一个数组，赋值为nums里面的值
    for(int i = 0; i < n; i++) {
        temp[i] = nums[i];
    }

    //这里的话，针对将对应temp数组里，按照平移后的位置赋值到nums对应的ind位置
    for(int i = 0; i < n; i++) {
        //取余是以右边的数n为准，右边的数控制范围
        int ind = (i + k) % n;
        nums[ind] = temp[i];
    }
}

环状替换
首先是这种方法可以在空间复杂度为O(1)的情况下，将原来数组的值赋值到对应位置
这里的话，可以总结规律成这样的，这里给定n和给定k，若是第一次遍历到头之后，没有直接回到起点，那么以后每次都多一点或者少一点，
这种情况的话，就一次就可以把所有元素遍历到了。 若是第一次直接遍历到头了，那么只能遍历这些元素，需要遍历多次才可以。
这里，我们从位置0开始，置换x = (0+k) mod n，之后在对(x+k) mod n继续替换，直到重新回到开始位置0，而且不论n为多少，k为多少，总会重新回到1
这里我们不知道有没有遍历完成所有的元素，有可能遍历完成了，也有可能没有遍历完成，所以，我们需要在下一个位置的元素继续遍历，这样直到将所有的
元素都遍历完成之后，那么我们就停止遍历。
注：这里第二种解法还没有完全弄明白，还需要在理解呀。

void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    //下面这个gcd的函数，可以通过力扣的编译器，但是本地因为版本的原因不能运行。
    //或者还有一种方法，另一种的方法是，当遍历了n个元素的时候自然停止。
    int count = __gcd(k, n);

    //这里最外层的循环是运行几次，也就是需要几个大圈才能将所有的元素遍历完。
    //这里有时候i从一个下标开始向后遍历，当遍历完成之后，ind又回到i的位置，这个是一定的。
    //但是有可能他不能将所有的元素遍历完成，也有可能将所有的元素遍历完成。
    //那么需要在几个位置遍历，需要通过gcd(n,k)得出。
    //这里也就是先从0位置开始，在从1位置开始，直到遍历完成为止。
    for(int i = 0; i < count; i++) {
        int ind = (i + k) % n; //下一个元素的位置
        int temp = nums[i];

        //这里是不断替换成下一个元素
        //首先，将第一个位置的元素保存在temp中
        //temp和下一个位置的值交换，这样的话temp就保存了下一个元素的值
        //总是将后面的位置赋值为temp，temp赋值为后面的值，这样temp总是保持最新的
        //当下一个位置是i的时候停止
        while(ind != i) {
            swap(temp, nums[ind]);
            ind = (ind + k) % n;
        }

        //这里不断向后移动的问题，就是要找个东西将当前的内容存进去
        //swap(nums[i], nums[ind]); 这样也是可以的，每次都用nums[i]存储
        //将temp赋值为i
        nums[i] = temp;
    }
}

数组翻转
我们将数组向后移动k次，移动k次之后，那么尾部的元素就会到前面去，而前面的元素就会到尾部去
[n-k, n-1] => [0, k-1]、[0~n-k-1] => [k, n-1]
1.所以我们这里首先将所有元素反转。这样尾部元素和前面的元素就可以交换了。
2.[0, k-1]的元素反转。
3.[k, n-1]的元素反转

void reverse(vector<int>& nums) {
    int n = nums.size();

    for(int i = 0; i < n / 2; i++) {
        int temp = nums[i];
        nums[i] = nums[n - i - 1];
        nums[n - i - 1] = temp;
    }
}
void reverser(vector<int>& nums, int i, int j) {
    while(i < j) {
        //swap(nums[start], nums[end]);
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        i++;
        j--;
    }
}
void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    //这里首先要对n取余，取余之后才能得到最小的移动步数
    k %= n;
    //得到步数之后，可以计算那些元素会移动到前面，那些元素会移动到后面
    reverser(nums, 0, n - 1);
    reverser(nums, 0, k - 1);
    reverser(nums, k, n - 1);
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    rotate(nums, 2);

    for(int i = 0; i < nums.size(); i++) {
        printf("%d", nums[i]);
    }

    return 0;
}