[LeetCode][Medium] 189. Rotate Array

Leetcode 網址: https://leetcode.com/problems/rotate-array/

題目說明:

給定一個長度為 n 的序列，往右旋轉 k 次 (k 保證為非負整數)，請給出向右旋轉 k 次後的序列

Follow up: O(1) extra space

Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

解題說明:

如果不知道何謂向右旋轉的話可以先從範例1中了解向右旋轉的定義，

接著我直覺的想法是，直接先把 k 個數字 swap 到最前面，接著在處理剩下的序列即可，

以範例 1 為例即是， [1, 2, 3, 4, 5, 6, 7] => [5, 6, 7, 4, 1, 2, 3]，

觀察剩下的序列可以發現，[4, 1, 2, 3] 又是往右旋轉 k 次的問題，

因此寫出遞迴即可解決此問題。

程式碼

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

結果

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Rotate Array.

Memory Usage: 9.6 MB, less than 97.97% of C++ online submissions for Rotate Array.