Swift实现数组循环右移的更优方案探讨

Nice question! Rotating an array K times efficiently is a common problem, and Swift gives us some clean, performant ways to avoid the slow naive approach (shifting elements one by one K times, which runs in O(K*N) time). Let's break down two solid solutions:

Approach 1: Slice and Concatenate (Simple & Readable) #

This method leverages Swift's array slicing to quickly split the array and recombine it in rotated order. It's straightforward and easy to maintain, though it creates a new array (so it uses O(N) space).

Code Implementation #

func rotate(_ nums: inout [Int], _ k: Int) {
    let count = nums.count
    // Handle edge cases: empty array or no rotation needed
    guard count > 0, k != 0 else { return }
    // Calculate effective rotation (rotating N times brings back the original array)
    let effectiveK = k % count
    
    // Split the array into two parts and concatenate in reversed order
    nums = Array(nums[count - effectiveK ..< count] + nums[0 ..< count - effectiveK])
}

How It Works #

For example, with A = [3, 8, 9, 7, 6] and K = 1:

• effectiveK = 1 % 5 = 1
• We take the last 1 element: [6]
• We take the first 4 elements: [3, 8, 9, 7]
• Concatenate them to get [6, 3, 8, 9, 7]

Time Complexity: O(N) (we're creating a new array with all N elements)
Space Complexity: O(N) (for the new array)

Approach 2: In-Place Rotation with Three Reversals (Space-Optimized) #

If you need to modify the array in place (no extra space beyond a few variables), the three-reversal technique is perfect. It runs in O(N) time with O(1) space.

The Idea #

1. Reverse the entire array.
2. Reverse the first effectiveK elements.
3. Reverse the remaining elements.

Code Implementation #

func rotateInPlace(_ nums: inout [Int], _ k: Int) {
    let count = nums.count
    guard count > 0, k != 0 else { return }
    let effectiveK = k % count
    
    // Step 1: Reverse the entire array
    reverseSubarray(&nums, start: 0, end: count - 1)
    // Step 2: Reverse the first 'effectiveK' elements
    reverseSubarray(&nums, start: 0, end: effectiveK - 1)
    // Step 3: Reverse the remaining elements
    reverseSubarray(&nums, start: effectiveK, end: count - 1)
}

// Helper function to reverse a subarray from 'start' to 'end' (inclusive)
private func reverseSubarray(_ nums: inout [Int], start: Int, end: Int) {
    var left = start
    var right = end
    while left < right {
        nums.swapAt(left, right)
        left += 1
        right -= 1
    }
}

Example Walkthrough #

Using A = [3, 8, 9, 7, 6] and K = 1:

1. Reverse entire array: [6, 7, 9, 8, 3]
2. Reverse first 1 element: [6, 7, 9, 8, 3] (no change here)
3. Reverse elements from index 1 to 4: [6, 3, 8, 9, 7]

Time Complexity: O(N) (each element is reversed twice, total operations are linear)
Space Complexity: O(1) (only using a few variables for indices)

Key Edge Cases to Handle #

• If the array is empty or has only one element: no rotation needed.
• If K is 0 or a multiple of the array length: rotating K times leaves the array unchanged, so we can skip processing.
• If K is larger than the array length: use K % count to get the effective number of rotations (since rotating N times brings back the original array).

内容的提问来源于stack exchange，提问作者Ali Jawad