LeetCode 189. Rotate Array

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        const int n = nums.size();
        vector<int> newArr(n);
        for (int i = 0; i < n; ++i)
            newArr[(i + k) % n] = nums[i];
        nums.assign(newArr.begin(), newArr.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        const int n = nums.size();
        k %= n;
        int cnt = gcd(n, k);
        for (int start = 0; start < cnt; ++start) {
            int currIndex = start;
            int currVal = nums[currIndex];
            do {
                int nextIndex = (currIndex + k) % n;
                int nextVal = nums[nextIndex];
                nums[nextIndex] = currVal;
                currIndex = nextIndex;
                currVal = nextVal;
            } while (currIndex != start);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
private:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end)
            swap(nums[start++], nums[end--]);
    }
};