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

题干懒人包

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

附注：尽量想越多种解法越好，想到之后可否利用空间複杂度 O(1) 完成

Input: nums = [1,2,3,4,5,6,7], k = 3Output: [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 - 10 <= k <= 105

解法

先用 tmp 纪录最后一段的数组切片(比方说上面那个例题，先用tmp纪录[5, 6, 7])将nums的第k项到最后一项用0到n-k项取代([4, 5, 6, 7]被[1, 2, 3, 4]取代)最后再将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

别人的正解

想法：

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

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