LeetCode: 189 旋转数组三种解法

[resse92]

第一种

一次把所有数字右移，每次移动一个。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (k <= 0) {
            return;
        }
        nums.insert(nums.begin(), nums[nums.size() - 1]);
        nums.pop_back();
        rotate(nums, k - 1);
    }
};

第二种

三次翻转，首先将前后两组数据先各自翻转一次，最后将整体所有数据翻转一次。

class Solution {
public:
    void rotated(vector<int> &nums, int start, int end) {
        int temp = 0;
        while (start < end) {
            temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start ++;
            end --;
        }
        return;
    }

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

第三种

从第一个数组依次向右移，记录被覆盖的数字，将覆盖的数字继续右移，知道最后所有数字都右移完成。

class Solution {
public:

    void rotate(vector<int>& nums, int k) {
        if (nums.empty() || k == 0)
            return;
        int length = nums.size();
        int start = 0;
        int i = 0;
        int cur = nums[i];
        int cnt = 0;

        while (cnt++ < length) {
            i = (i + k) % length;
            int t = nums[i];
            nums[i] = cur;
            if (i == start) {
                ++start;
                ++i;
                cur = nums[i];
            } else {
                cur = t;
            }
        }
    }
};