LeetCode 189. 旋转数组 Rotate Array

【题目描述】
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

【示例1】

输入: [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】

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

【思路1】
1、暴力解决
2、每次只移动一个元素，最后移动k%nums.count * num.count次
3、时间复杂度O(k*n)
4、空间复杂度O(1)

Swift代码实现：

func rotate(_ nums: inout [Int], _ k: Int) {
    for _ in 0..<k%nums.count {
        let tmp = nums.last!
        var lenth = nums.count-1
        while lenth > 0 {
            nums[lenth] = nums[lenth-1]
            lenth-=1
        }
        nums[0] = tmp
    }
}

【思路2】
1、反转
2、先把整个数组倒序排列
3、反转前k-1个元素
4、再反转k-num.count-1元素
5、时间复杂度O(n)
6、空间复杂度O(1)

Swift代码实现：

func rotate(_ nums: inout [Int], _ k: Int) {
    let kk = k%nums.count
    rotate(&nums, start: 0, end: nums.count-1)
    rotate(&nums, start: 0, end: kk-1)
    rotate(&nums, start: kk, end: nums.count-1)
}

func rotate(_ nums:inout [Int],start:Int,end:Int) {
    var s = start
    var e = end
    
    while s < e {
        let tmp = nums[s]
        nums[s] = nums[e]
        nums[e] = tmp
        s+=1
        e-=1
    }
}

【思路3】
1、使用额外空间数组
2、数组切片
3、不符合题意
4、代码略