拷貝工程師

 

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?

 

 

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]

 

public class Solution {
    public void Rotate(int[] nums, int k)
        {
            if (k == 0) return;
            k = k % nums.Length;
            Reverse(nums,0,nums.Length-1);
            Reverse(nums, 0, k-1);
            Reverse(nums, k, nums.Length-1);

        }

        public void Reverse(int[] nums, int star,int end)
        {
            while (star < end) {
                int temp = nums[star];
                nums[star] = nums[end];
                nums[end] = temp;
                star++;
                end--;
            }
        }
}