LeetCode

題目：旋轉(zhuǎn)數(shù)組

給定一個(gè)數(shù)組，將數(shù)組中的元素向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(shù)。

示例 1:

輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

示例 2:

輸入: [-1,-100,3,99] 和 k = 2
輸出: [3,99,-1,-100]
解釋: 
向右旋轉(zhuǎn) 1 步: [99,-1,-100,3]
向右旋轉(zhuǎn) 2 步: [3,99,-1,-100]

說明:

-盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個(gè)問題。
-要求使用空間復(fù)雜度為 O(1) 的 原地 算法。

方法一

執(zhí)行用時(shí)：2348 ms
保存最后一個(gè)數(shù)字，然后使用循環(huán)將數(shù)字往后推一位。內(nèi)部循環(huán)n-1次(n=nums.count)，外部循環(huán)k次，總共循環(huán)k*(n-1)次。

class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        var cnt = k
        while(cnt > 0){
            let lastnum = nums.last
            var idx = nums.count-1
            while(idx > 0) {
                nums[idx] = nums[idx-1]
                idx -= 1
            }
            nums[0] = lastnum!
            cnt -= 1
        }
    }
}

方法二

執(zhí)行用時(shí) :44 ms, 在所有 Swift 提交中擊敗了100.00%的用戶
內(nèi)存消耗 :20.6 MB, 在所有 Swift 提交中擊敗了5.97%的用戶
將數(shù)組倒序，然后在倒序的基礎(chǔ)上0-k再倒序，k-(cnt-1)倒序。

class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        if nums.isEmpty || k <= 0 {
            return
        }
        
        let cnt = nums.count
        let j = k%cnt
        func reverse(_ start: Int, _ end: Int){
            var start = start
            var end = end
            while(start < end){
                let temp = nums[start]
                nums[start] = nums[end]
                nums[end] = temp
                start += 1
                end -= 1
            }
        }
        reverse(0, cnt-1)
        reverse(0, j-1)
        reverse(j, cnt-1)
    }
}

方法三