Algorithem_ReverseArray

Algorithem_ReverseArray#

給定一個數組，將數組向右旋轉 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]

ReverseArray#

解法 1：

循環彈出末尾元素，放入數組第一個位置，每彈出一次 k-1，直到 k=0 截止


class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        // 解法1
        var times = k
        while (times > 0) {
            let last = nums.removeLast()
            nums.insert(last, at: 0)
            times -= 1
        }
    }

能達到最終結果，但是跟算法無法，沒有 reverseArrray

解法 2：

reverseArray 的邏輯是：比如有 nums=[1, 2, 3, 4, 5, 6, 7], key = 3，則對 [1, 2, 3, 4] rotate 得到 [4, 3, 2, 1]，對 [5, 6, 7] rotate 得到 [7, 6, 5]，然後合併得到 [4, 3, 2, 1, 7, 6, 5]，再 rotate 得到 [5, 6, 7, 1, 2, 3, 4]

代碼如下：


class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        // 解法2
        let count = nums.count
        let tempK = k % count
        reverse(&nums, 0, count - tempK - 1)
        reverse(&nums, count - tempK, count-1)
        reverse(&nums, 0, count-1)
    }
    
    func reverse(_ nums: inout [Int], _ i: Int, _ j: Int) {
        var mutI = i
        var mutJ = j
        while (mutI < mutJ) {
            nums.swapAt(mutI, mutJ)
            mutI += 1
            mutJ -= 1
        }
    }
}