哈囉大家～
今天我們來聊聊一個看似簡單但總是讓人「啊啊啊！」的經典題目：「Rotate Array」～

也就是說，我們要把陣列裡的數字轉來轉去！
這題一看就覺得好像沒什麼，轉幾圈不就好啦？但其實內部的邏輯還是有點小巧思的！
🤓 當然啦，我們不是要你暴力地轉很多次，而是要用聰明的方式一次到位，這樣才是工程師的浪漫～ 💡❤️

題目：Rotate Array

難度：Medium

主題：Array, Two Pointers

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

• Input: nums = [1,2,3,4,5,6,7], k = 3
• Output: [5,6,7,1,2,3,4]
• Explanation:
  • Rotate 1 step 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]

Example 2:

• Input: nums = [-1,-100,3,99], k = 2
• Output: [3,99,-1,-100]
• Explanation:
  • Rotate 1 step to the right: [99,-1,-100,3]
  • Rotate 2 steps to the right: [3,99,-1,-100]

中文描述

給定一個整數數組 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]

實作

function rotate(nums: number[], k: number): void {
  // Step 1: Reduce k if it's greater than the array length
  k = k % nums.length;

  // Step 2: Reverse the entire array
  reverse(nums, 0, nums.length - 1);

  // Step 3: Reverse the first k elements
  reverse(nums, 0, k - 1);

  // Step 4: Reverse the remaining elements
  reverse(nums, k, nums.length - 1);
}

function reverse(arr: number[], start: number, end: number): void {
  while (start < end) {
    // Swap elements
    [arr[start], arr[end]] = [arr[end], arr[start]];
    start++;
    end--;
  }
}

解題脈絡：

這題的核心思路是運用「反轉法」，這個小技巧讓我們不用笨笨地一個個轉，而是一次搞定所有位置。具體步驟如下：

1. 反轉整個數組：這步驟會把整個數組顛倒過來。
2. 反轉前 k 個元素：接著，我們反轉前面 k 個已經被移動過去的元素，讓它們回到應有的位置。
3. 反轉剩下的元素：最後，反轉剩餘的部分，這樣就完美達成右旋 k 步的效果啦！

本次要點：

• 反轉是關鍵，將原來的多次移動問題簡化為三次反轉。
• 時間複雜度 O(n)，瞬間變身效率高手！

希望你們今天的腦袋也能這樣「靈光一轉」，和數字一樣轉出好運！有問題隨時留言哦～我們下次見！🚀