题目描述:

方法1:用一个新数组存最后 k 个数字,然后把最后 k 个数字之前的数字依次向后移动 k 位,最后把新数组中数组存回原数组头部

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> temp(k);
        for(int i=nums.size()-k; i<nums.size(); i++){
            temp.push_back(nums[i]);
        }
        for(int i=nums.size()-k-1;i>=0;i--){
            nums[i+k] = nums[i];
        }
        for(int i=0;i<k;i++){
            nums[i] = temp[i];
        }
    }
};

出错,因为 push_back 是向数组末尾添加数字,应该把 vector<int> temp(k) 改为 vector<int> temp(0)

方法2:遍历原数组,将原数组下标为 i 的元素放至新数组下标为 (i+k) % n 的位置,最后将新数组拷贝至原数组

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> temp(n);
        for(int i=0;i<n;i++) temp[(i+k) % n] = nums[i];
        nums = temp;
    }
};

方法3:整体数组反转一次,然后前k个数字反转一次,最后剩下数字再反转一次

class Solution {
public:
    void reverse(vector<int>& temp, int s, int e){
        int n = (e+s)/2;
        int m = 0;
        for(int i=s;i<=n;i++){
            m = temp[i];
            temp[i] = temp[e];
            temp[e] = m;
            e = e-1;
        }
    }

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

出错了三次:第一次,n写成(e-s)/2;第二次,没有加 if(k == 0) return,而 reverse(nums,0,-1)报错;第三次,if(k == 0) return写在了第一行,但是k为nums.size()时,k % nums.size()任然为0,更好的方法是,reverse 时,用 while 判断 s 和e 关系:

class Solution {
public:
    void reverse(vector<int>& temp, int s, int e){
        while(s < e){
            swap(temp[s++],temp[e--]);
        }
    }

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