leetcode：189. 轮转数组

题目来源

• leetcode：189. 轮转数组

题目描述

题目解析

使用临时数组

可以用一个临时数组，先把原数组的值存放到一个临时数组中，然后再把临时数组的值重新赋给原数组，重新赋值的时候要保证每个元素都要后移k位，如果超过数组长度就重头开始

class Solution {
    
public:
    // 1 <= nums.length <= 10^5
    void rotate(vector<int>& nums, int k) {
    
        int N = nums.size();
        k = k % N;
        if(k == 0){
    
            return;
        }
        
        std::vector<int> temp(N);
        //把原数组值放到一个临时数组中，
        for (int i = 0; i < N; i++) {
    
            temp[i] = nums[i];
        }
        //然后在把临时数组的值重新放到原数组，并且往右移动k位
        for (int i = 0; i < N; i++) {
    
            nums[(i + k) % N] = temp[i];
        }
    }
};

多次反转

class Solution {
    
public:
    // 1 <= nums.length <= 10^5
    void rotate(vector<int>& nums, int k) {
    
        int N = nums.size();
        k = k % N;
        if(k == 0){
    
            return;
        }
        
        std::reverse(nums.begin(), nums.end());
        std::reverse(nums.begin(), nums.begin() + k);
        std::reverse(nums.begin() + k, nums.end());
    }
};

连环怼

class Solution {
    
public:
    // 每次把一个元素弄到对应位置去
    // 1 <= nums.length <= 10^5
    void rotate(vector<int>& nums, int k) {
    
        int N = nums.size();
        k = k % N;
        int count = 0;         // 记录交换位置的次数，n个同学一共需要换n次
        for (int start = 0; count < N; ++start) {
    
            int curr = start; // 从0位置开始换位子
            int prev = nums[curr];
            do{
    
                //下一个坐标
                int next = (curr + k) % N;
                //交换
                int tmp = nums[next];
                nums[next] = prev;
                prev = tmp;
                //更新当前位置
                curr = next;
                count++;
            }while (start != curr);  // 循环暂停，回到起始位置，角落无人
        }
    }
};