iT邦幫忙

0

[用 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

尚未有邦友留言

立即登入留言