LeetCode
题目：旋转数组
给定一个数组，将数组中的元素向右移动 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]
说明:
-尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
-要求使用空间复杂度为 O(1) 的 原地 算法。
方法一
执行用时：2348 ms
保存最后一个数字，然后使用循环将数字往后推一位。内部循环n-1次(n=nums.count)，外部循环k次，总共循环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
}
}
}
方法二
执行用时 :44 ms, 在所有 Swift 提交中击败了100.00%的用户
内存消耗 :20.6 MB, 在所有 Swift 提交中击败了5.97%的用户
将数组倒序，然后在倒序的基础上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)
}
}
