Leetcode skimming ---189

subject ： Give you an array , Rotate the elements in the array to the right  k  A place , among  k  It is a non negative number .

Input ：nums = [1,2,3,4,5,6,7],  k = 3

Output ：[5,6,7,1,2,3,4]

Method 1 ： Use extra arrays

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        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());
    }
};

Complexity analysis

Time complexity ：O(n)

Spatial complexity ：O(n)

Method 2 ： Circular substitution

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                swap(nums[next], prev);
                current = next;
            } while (start != current);
        }
    }
};

Complexity analysis

Time complexity ：O(n)

Spatial complexity ：O(1)

Method 3 ： An array of reverse

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }
    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);
    }
};

Complexity analysis

Time complexity ：O(n)

Spatial complexity ：O(1)