tsanmmmm2000's Tech Blog

Question

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].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

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

Thinking

最簡單的方式是一步一步將尾端的元素慢慢地移到最前端，而其中若發生k大於n的情況時，在開始計算前需要先調整一下k，因為實際上我們不需要這麼多步驟

public class Solution {
    public void Rotate(int[] nums, int k) {
        k = k % nums.Length;
        while(k > 0)
        {
            var last = nums[nums.Length - 1];
            for (var i = 0; i < nums.Length; i++)
            {
                var temp = nums[i];
                nums[i] = last;
                last = temp;
            }
            k--;
        }
    }
}

這解法雖然有符合題目說的空間複雜度O(1)，但時間複雜度卻是O(k*n)，結果甚至會出現TLE。我們在討論區又看到一個相當漂亮的解法，概念是先準備一組Reverse Method，內部邏輯與前述方法大致相同，即將尾端的元素移到前端，再來我們先假設n=7、k=3、陣列為[1,2,3,4,5,6,7]，實際操作如下

1. Reverse全部：[7,6,5,4,3,2,1]
2. Reverse前k個元素：[5,6,7,4,3,2,1]
3. Reverse後n-k個元素：[5,6,7,1,2,3,4]

只要三個步驟就可以算出答案，原理應該不難理解，這樣時間複雜度便降到了O(n)

My C# Solution

public class Solution {
    public void Rotate(int[] nums, int k) {
        k = k % nums.Length;
        Reverse(nums, 0, nums.Length - 1);
        Reverse(nums, 0, k - 1);
        Reverse(nums, k, nums.Length - 1);
    }
    
    private void Reverse(int[] nums, int start, int end)
    {
        while(start < end)
        {
            var temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}