189. 旋转数组
给你一个数组，将数组中的元素向右轮转
k个位置，其中k是非负数。
示例一：
输入: 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]
示例二：
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
解题方法一：使用额外的数组
class Solution {
func rotate(_ nums: inout [Int], _ k: Int) {
let count = nums.count
guard count >= 2 && count != k else {
return
}
var result = [Int](repeating: -1, count: count)
let k = k % count
for i in 0..<k {
let index = count - k + i
result[i] = nums[index]
}
for i in 0..<(count - k) {
result[k + i] = nums[i]
}
for i in 0..<count {
nums[i] = result[i]
}
}
}
解题思路:
我们可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，先遍历最后 k 个元素，并把它们加入到新数组的前面。之后再遍历数组的前 count - k 个数据，加入新数组的后面。最后将新数组拷贝至原数组即可。
复杂度分析
- 时间复杂度：
O(n)，其中n为数组的长度。 - 空间复杂度：
O(n)。
解题方法二：数组翻转
class Solution {
func rotate(_ nums: inout [Int], _ k: Int) {
let count = nums.count
guard count >= 2 || count != k else { return }
let k = k % count
reverse(&nums, 0, count - 1)
reverse(&nums, 0, k - 1)
reverse(&nums, k, count - 1)
}
func reverse(_ nums: inout [Int], _ start: Int, _ end: Int) {
var left = start
var right = end
while left < right {
nums.swapAt(left, right)
left += 1
right -= 1
}
}
}
解题思路:
该方法基于如下的事实：当我们将数组的元素向右移动 k 次后，尾部 k%n 个元素会移动至数组头部，其余元素向后移动 k%n 个位置。
该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的 k%n 个元素就被移至数组头部，然后我们再翻转 [0,k%n−1] 区间的元素和 [k%n,n−1] 区间的元素即能得到最后的答案。
复杂度分析
- 时间复杂度：
O(n)，其中n为数组的长度。每个元素被翻转两次，一共n个元素，因此总时间复杂度为O(2n)=O(n)。 - 空间复杂度：
O(1)。