189. Rotate Array

Medium

Description

給定整數陣列 nums，將陣列向右旋轉 k 步。

Example:

Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4]

Intuition#

核心思路：三次反轉法 – 先全部反轉，再分別反轉前 k 個和後 n-k 個。

旋轉 k 步 = 把最後 k 個元素搬到最前面
三次反轉可以巧妙地達成這個效果：
1. 全部反轉：[7,6,5,4,3,2,1]
2. 反轉前 k 個：[5,6,7,4,3,2,1]
3. 反轉後 n-k 個：[5,6,7,1,2,3,4]
記得先對 k 取模，避免 k > n 的情況

Approaches#

1: 額外陣列#

概念: 建立新陣列，把每個元素放到 (i + k) % n 的位置
時間複雜度: O(n)
空間複雜度: O(n) - 額外陣列

class Solution {
    fun rotate(nums: IntArray, k: Int): Unit {
        val n = nums.size
        val result = IntArray(n)
        for (i in nums.indices) {
            result[(i + k) % n] = nums[i]
        }
        for (i in nums.indices) nums[i] = result[i]
    }
}

⭐2: 三次反轉#

概念: 全部反轉 -> 反轉前 k 個 -> 反轉後 n-k 個
時間複雜度: O(n) - 三次線性掃描
空間複雜度: O(1) - 原地操作

class Solution {
    fun rotate(nums: IntArray, k: Int): Unit {
        val n = nums.size
        val step = k % n
        reverse(nums, 0, n - 1)
        reverse(nums, 0, step - 1)
        reverse(nums, step, n - 1)
    }

    private fun reverse(nums: IntArray, start: Int, end: Int) {
        var left = start
        var right = end
        while (left < right) {
            val temp = nums[left]
            nums[left] = nums[right]
            nums[right] = temp
            left++
            right--
        }
    }
}

務必先 k % n，否則 k >= n 時反轉範圍會出錯。當 step == 0 時不需任何操作。

🔑 Takeaways#

Pattern: 三次反轉法（Reverse Three Times）是陣列旋轉的經典 O(1) 空間做法
關鍵技巧: 反轉子陣列是 Two Pointers 的基本操作；此方法也適用於字串旋轉問題