Rotate Array

旋转数组

Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Hint:
Could you do it in-place with O(1) extra space?

要求空间O(1)。因此要做 in place 的数组操作。

思路一

类似插入排序的操作，将需要旋转的数字逐个左移到数组的左端。时间复杂度O(n^2)。

Time Limit Exceeded

思路二

reverse整个数组，再分别reverse 需要旋转的子数组和不需要旋转的字数组。
以[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] , n = 10, k = 3 为例。

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[8, 9, 10, 7, 6, 5, 4, 3, 2, 1]
[8, 9, 10, 1, 2, 3, 4, 5, 6, 7]

class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        let count = nums.count
        let reverse = k % count
        nums.reverse()
        nums[0..<reverse].reverse()
        nums[reverse..<count].reverse()
    }
}

刚开始都是自己写reverse函数，后来发现swift的ArraySlice的reverse是 in place 的，于是直接用reverse method。代码清爽好多。

Runtime Distribution

出乎意料，运行时间和cpp不相上下，远好于golang。有点诧异，比golang强这么多，原以为 golang 会更快。

Pasted Graphic副本.jpg