LeetCode 0189

题目

189. Rotate Array

解法 1 暴力法

每次旋转 1 个元素，总计旋转 k 次

func rotate(_ nums: inout [Int], _ k: Int) {
    if k == 0 { return }
    for i in stride(from: 0, to: nums.count - 1, by: 1) {
        // 交换下标 i 与 nums.count - 1 的两个数
        nums[i] = nums[i] ^ nums[nums.count - 1]
        nums[nums.count - 1] = nums[i] ^ nums[nums.count - 1]
        nums[i] = nums[i] ^ nums[nums.count - 1]
    }
    rotate(&nums, k - 1)
}

um… 完美的超出时间限制了

解法 2 三次反转

对于给定的数组长度 n 反转次数 k，会有 k%n 个尾部元素被移动到最前面。

以题干中的 Example 为例，按照 k=3, n=7 将原数组 [1,2,3,4,5,6,7] 分为 [1,2,3,4] 和 [5,6,7] 两个部分。

第一次反转

反转第一部分得到结果 [4,3,2,1,5,6,7]

第二次反转

反转第二部分得到结果 [4,3,2,1,7,6,5]

第三次反转

反转全部得到答案 [5,6,7,1,2,3,4]

func rotate3Times(_ nums: inout [Int], _ k: Int) {
    var k = k
    k %= nums.count
    func reverse(_ start: Int, _ end: Int) {
        var start = start
        var end = end
        while start < end {
            nums[start] = nums[start] ^ nums[end]
            nums[end] = nums[start] ^ nums[end]
            nums[start] = nums[start] ^ nums[end]
            start += 1
            end -= 1
        }
    }
    // 第一次反转
    reverse(0, nums.count - 1 - k)
    // 第二次反转
    reverse(nums.count - k, nums.count - 1)
    // 第三次反转
    reverse(0, nums.count - 1)
}