[用 Python 解 LeetCode] (005) 189. Rotate Array

题干懒人包

给一个数组，旋转数组 K 次，K 非负数，如以下

附注：尽量想越多种解法越好，想到之後可否利用空间复杂度 O(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 <= nums.length <= 2 * 104
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

解法

1. 先用 tmp 纪录最後一段的数组切片(比方说上面那个例题，先用tmp纪录[5, 6, 7])
2. 将nums的第k项到最後一项用0到n-k项取代([4, 5, 6, 7]被[1, 2, 3, 4]取代)
3. 最後再将tmp放回去 ([1, 2, 3]被[5, 6, 7]取代)。

缺点：

很快，但空间复杂度并非 O(1)

class Solution:
    def rotate(self, nums, k: int) -> None:
        n = len(nums)
        # k 取余数，比方说等於n根本不用旋转
        k %= n
        if k != 0:
            # 1
            tmp = nums[-k:]
            # 2
            nums[k:n] = nums[:n - k]
            # 3
            nums[0:k] = tmp

别人的正解

想法：

1. 首先先将整个数组翻转一次
2. 接下来看k多少决定左边以及右边的分界
3. 翻转左边，然後翻转右边

1. [1,2,3,4,5,6,7] -> [7, 6, 5, 4, 3, 2, 1] 
3. [7, 6, 5, 4, 3, 2, 1] -> [5, 6, 7, 4, 3, 2, 1]
3. [5, 6, 7, 4, 3, 2, 1] -> [5, 6, 7, 1, 2, 3, 4]

所以我们该设计一个可以翻转整个数组的函数

class Solution:
        def rotate(self, nums, k: int) -> None:
            k %= len(nums)
            
            def reverse(nums, i, j):
                while i < j:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
                    j -= 1
            
            reverse(nums, 0, len(nums)-1)
            reverse(nums, 0, k-1)
            reverse(nums, k, len(nums)-1)  

reverse 函数

可以把 i 想像成头，j 想像成尾巴，当他们头小於尾时俩俩交换，并各自加减一

# 比方说reverse([1, 2, 3, 4, 5, 6, 7], 0, 3)
# 第一次
[1, 2, 3, 4, 5, 6, 7] -> [4, 2, 3, 1, 5, 6, 7]
# 第二次(注意这次是2跟3交换了)
[4, 2, 3, 1, 5, 6, 7] -> [4, 3, 2, 1, 5, 6, 7]
# 准备第三次时i现在等於2，j现在等於1，因此停止

记得这里 while 的条件最好不要设等於 (建议而已)，因为比方说今天数组的长度是奇数，那可能 i += 1、j -= 1，会遇到相同的值(i 会等於 j)，当然要看设计这个函数的需求是甚麽。

def reverse(nums, i, j):
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i += 1
        j -= 1