Swift 旋转数组 - LeetCode
旋转数组
将包含 n 个元素的数组向右旋转 k 步。
例如，如果 n = 7 , k = 3，给定数组
[1,2,3,4,5,6,7] ，向右旋转后的结果为
[5,6,7,1,2,3,4]。
注意: 尽可能找到更多的解决方案，这里最少有三种不同的方法解决这个问题。
提示: 要求空间复杂度为 O(1)
-1）第一获取最高位的数字，第二把其他位上的数字都抬高一位，第三把最初获得最高位的数字赋值到最低位置上。我觉得这个算法没啥问题啊。。。???可是过不了最后一个测试用例。。。（超出时间限制），好吧。。。希望有大神解惑
代码如下：
class Solution {
func rotate(_ nums: inout [Int], _ k: Int) {
var terns = k % nums.count
if nums.isEmpty || terns == 0 {
return
}
while terns > 0 {
var temp = 0
temp = nums.last!
for i in (0..<(nums.count - 1)).reversed() {
nums[i + 1] = nums[i]
}
nums[0] = temp
terns -= 1
}
}
}-2)取余数，比如长度为5的数组，向右旋转2步 1，2，3，4，5 4，5，1，2，3
newNums[(0 + 2) % 5] = nums[0] 即新数组newNums[2] = nums[0] = 1
newNums[(4 + 2) % 5] = nums[4] 即新数组newNums[1] = nums[4] = 5
...数字的位置加2之后大于5的都要再从0号位置重新开始计算剩余的步子。这点特性就可以很好的用到求余。 代码如下：
class Solution {
func rotate(_ nums: inout [Int], _ k: Int) {
var terns = k % nums.count
if nums.isEmpty || terns == 0 {
return
}
var newNums = nums
for i in 0..<nums.count {
newNums[(i + terns) % nums.count] = nums[i]
}
nums = newNums
}
}执行时间：28ms
-3)在网上找到一种其他的思路：先把前n-k个数字翻转一下，再把后k个数字翻转一下，最后再把整个数组翻转一下 代码如下：
class Solution {
func rotate(_ nums: inout [Int], _ k: Int) {
let terns = k % nums.count
if nums.isEmpty || terns == 0 {
return
}
let middle = nums.count - terns
reverse(&nums, s: 0, e: middle - 1)
reverse(&nums, s: middle, e: nums.count - 1)
reverse(&nums, s: 0, e: nums.count - 1)
}
func reverse(_ nums: inout [Int], s: Int, e: Int) {
var s = s
var e = e
while s < e {
let temp = nums[s]
nums[s] = nums[e]
nums[e] = temp
s += 1
e -= 1
}
}
}执行时间：32ms
其他算法，我就不写了。。。。因为不会???
开始用Swift学习算法中，在LeetCode中开始做初级算法这一章节，将做的题目在此做个笔记吧。
举报
腾讯云开发者
