[LeetCode] 189. Rotate Array

Medium
Related Topics: Array / Math / Two Pointers
LeetCode Source

解题想法

这里初始化 l 是 nums 的长度
蛮直观的解法，直接在 l - k 的地方把 nums 切开，之后将后半部放到前面
不过要注意的一点是，有时候 k 会大于 l，所以记得 k = k % l

Python

class Solution:    def rotate(self, nums: List[int], k: int) -> None:        """        Do not return anything, modify nums in-place instead.        """        l = len(nums)        k = k % l        nums[:] = nums[l-k:] + nums[:l-k]        return

Python 解法有点简单，所以自己建议是多用其他语言解题

C++

class Solution {public:    void rotate(vector<int>& nums, int k) {        int l = nums.size();        k = k % l;        vector<int> temp(nums.begin() + l - k, nums.end());        temp.insert(temp.end(), nums.begin(), nums.begin() + l - k);        nums = temp;    }};

这解法不是 in-place 解，我在这多宣告一个 temp 来放 nums 的后半部
后面用 insert 将原先 nums 的前半部放在 temp 的后面，最后 temp 取代 nums

有鉴于 C++ 解法并非 in-place，所以有另一种解法，用 reverse()
做法是 reverse() 三次，后面两步可以交换顺序执行

解题想法

Python

class Solution(object):    def rotate(self, nums, k):        """        :type nums: List[int]        :type k: int        :rtype: None Do not return anything, modify nums in-place instead.        """        k = k % len(nums)        nums.reverse()        nums[k:] = reversed(nums[k:])        nums[:k] = reversed(nums[:k])

nums.reverse() 反转整个 list
而透过 reversed(nums[k:]) 反转 index k 到 l 的 list
reversed(nums[:k]) 反转 index 0 到 k - 1 的 list

C++

class Solution {public:    void rotate(vector<int>& nums, int k) {        k = k % nums.size();        reverse(nums.begin(), nums.end());        reverse(nums.begin(), nums.begin() + k);        reverse(nums.begin() + k, nums.end());    }};

这系列文被记录在 Top Interview 150 Series