LeetCode 熱題 100 | 189. 輪轉數組

大家好，今天我們來解決一道經典的算法題——輪轉數組。這道題在LeetCode上被標記為中等難度，要求我們將數組中的元素向右輪轉 k 個位置。下面我將詳細講解解題思路，并附上Python代碼實現。

---

問題描述

給定一個整數數組 nums，將數組中的元素向右輪轉 k 個位置，其中 k 是非負數。要求原地操作，不能使用額外的數組空間。

示例1：

輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉 1 步: [7,1,2,3,4,5,6]
向右輪轉 2 步: [6,7,1,2,3,4,5]
向右輪轉 3 步: [5,6,7,1,2,3,4]

示例2：

輸入: nums = [-1,-100,3,99], k = 2
輸出: [3,99,-1,-100]
解釋: 
向右輪轉 1 步: [99,-1,-100,3]
向右輪轉 2 步: [3,99,-1,-100]

---

解題思路

核心思想

1. 三次反轉法：

   • 首先反轉整個數組。
   • 然后反轉前 k 個元素。
   • 最后反轉剩下的 n - k 個元素。

2. 原地操作：

   • 通過反轉操作，避免使用額外的空間。

---

Python代碼實現

def rotate(nums, k):n = len(nums)k = k % n  # 處理k大于數組長度的情況def reverse(start, end):while start < end:nums[start], nums[end] = nums[end], nums[start]start += 1end -= 1reverse(0, n - 1)  # 反轉整個數組reverse(0, k - 1)   # 反轉前k個元素reverse(k, n - 1)   # 反轉剩下的元素# 測試示例
nums1 = [1, 2, 3, 4, 5, 6, 7]
nums2 = [-1, -100, 3, 99]rotate(nums1, 3)
rotate(nums2, 2)print(nums1)  # 輸出: [5, 6, 7, 1, 2, 3, 4]
print(nums2)  # 輸出: [3, 99, -1, -100]

---

代碼解析

1. 處理 k 大于數組長度的情況：

   • 使用 k = k % n 確保 k 在數組長度范圍內。

2. 定義反轉函數：

   • reverse 函數用于反轉數組中從 start 到 end 的部分。

3. 三次反轉操作：

   • 第一次反轉整個數組，將后 k 個元素移到前面，但順序相反。
   • 第二次反轉前 k 個元素，恢復其原始順序。
   • 第三次反轉剩下的 n - k 個元素，恢復其原始順序。

4. 原地操作：

   • 直接在原數組上進行操作，不需要額外的空間。

---

復雜度分析

• 時間復雜度：O(n)，其中 n 是數組的長度。我們只需要遍歷數組三次。
• 空間復雜度：O(1)，只使用了常數個額外空間。

---

示例運行

示例1

輸入: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
輸出: [5, 6, 7, 1, 2, 3, 4]

示例2

輸入: nums = [-1, -100, 3, 99], k = 2
輸出: [3, 99, -1, -100]

---

進階：其他解法

除了三次反轉法，我們還可以使用其他方法解決這個問題：

方法一：使用額外數組

def rotate_extra(nums, k):n = len(nums)k = k % nrotated = nums[-k:] + nums[:-k]nums[:] = rotated

• 時間復雜度：O(n)
• 空間復雜度：O(n)

方法二：環狀替換

def rotate_cyclic(nums, k):n = len(nums)k = k % ncount = 0start = 0while count < n:current = startprev = nums[start]while True:next_idx = (current + k) % nnums[next_idx], prev = prev, nums[next_idx]current = next_idxcount += 1if current == start:breakstart += 1

• 時間復雜度：O(n)
• 空間復雜度：O(1)

---

總結

通過使用三次反轉法，我們可以高效地將數組中的元素向右輪轉 k 個位置，同時保持原地操作。這種方法既簡單又高效，適合大多數場景。希望這篇題解對大家有所幫助，如果有任何問題，歡迎在評論區留言討論！

關注我，獲取更多算法題解和編程技巧！