[Swift]LeetCode189.旋转数组|RotateArray

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9726724.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

给定一个数组，将数组中的元素向右移动 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) 的原地算法。

48ms

 1 class Solution {
 2     func rotate(_ nums: inout [Int], _ k: Int) {
 3         guard nums.count > 1 else {
 4             return
 5         }
 6         
 7         guard k > 0 else {
 8             return
 9         }
10         
11         let k = k % nums.count        
12         nums = Array(nums[(nums.count - k)..<nums.count]) + Array(nums[0..<(nums.count - k)])        
13     }
14 }

48ms

 1 class Solution {
 2     func rotate(_ nums: inout [Int], _ k: Int) {
 3          let n = nums.count
 4         let numRoations = k % n
 5         var rotated = [Int]()
 6         for i in n-numRoations..<n {
 7             rotated.append(nums[i])
 8         }
 9         for j in 0..<n-numRoations {
10             rotated.append(nums[j])
11         }
12         nums = rotated
13     }
14 }

52ms

 1 class Solution {
 2     func rotate(_ nums: inout [Int], _ k: Int) {
 3         rotate1(&nums, k)
 4     }
 5     
 6     func rotate1(_ nums: inout [Int], _ k: Int) {
 7         var r: [Int] = Array(repeating: 0, count: nums.count)
 8         var kk = nums.count - (k % nums.count)
 9         for i in 0..<nums.count {
10             r[i] = nums[(i + kk) % nums.count]
11         }
12         for (i, num) in r.enumerated() {
13             nums[i] = num
14         }
15     }
16 }

56ms

 1 class Solution {
 2     func rotate(_ nums: inout [Int], _ k: Int) {
 3         guard nums.count > 0, k > 0 else {
 4             return
 5         }
 6         
 7         let k = k%nums.count
 8         
 9         rotate(&nums, 0, nums.count-k-1)
10         rotate(&nums, nums.count-k, nums.count-1)
11         rotate(&nums, 0, nums.count-1)
12     }
13     
14     private func rotate(_ nums: inout [Int], _ left: Int, _ right: Int) {
15         if left == right || nums.count == 0 { return }
16         
17         var i = left, j = right
18         
19         while i < j {
20             let temp = nums[i]
21             nums[i] = nums[j]
22             nums[j] = temp
23             i += 1
24             j -= 1
25         }
26     }
27 }

64ms

1 class Solution {
2     func rotate(_ nums: inout [Int], _ k: Int) {
3         var n = nums.count
4         let ind = n-1-k%n
5         nums += nums[0...ind]
6         nums.removeSubrange(0...ind)
7     }
8 }