Brooke

一、題目

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

 

Example 1:

Input: nums = [1,2,3,4,5,6,7], 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: nums = [-1,-100,3,99], 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]

 

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

 

二、程式作法

/*寫法二*/
public class Solution
{
    public void Rotate(int[] nums, int k)
    {
        Array.Reverse(nums);
        Array.Reverse(nums, 0, k % nums.Length);
        Array.Reverse(nums, k % nums.Length, nums.Length - k % nums.Length);
    }
}

/*寫法一*/
/*
public class Solution
{
    public void Rotate(int[] nums, int k)
    {
        int[] result = new int[nums.Length];

        for (int i = 0; i < nums.Length; i++)
        {
            result[(i + k) % nums.Length] = nums[i];
        }

        for (int i = 0; i < result.Length; i++)
        {
            nums[i] = result[i];
        }
    }
}
*/

 

三、思路筆記

題目要的結果是將一個陣列裡的元素往右旋轉 k 個位置。

我的做法是宣告一個相同長度的陣列，用來放新旋轉元素，

然後將該陣列複製回原陣列裡。

第二種解法我是看別人解的方式，感覺有點 trick，參考就好，

此解法不需要額外空間，時間複雜度為 O(1)，

做法為先將原本的陣列做 reverse，然後個別 reverse 從零開數 k 個元素，

與剩下的 nums.Length - k 個元素之後就是答案