卖萌的弱渣

I am stupid, I am hungry.

Rotate Array

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?

Solution

  • if n = 7 and k = 3
  • Reverse the whole array: [1 2 3 4 5 6 7] => [7 6 5 4 3 2 1]
  • Reverse array[0,k]: [7 6 5 4 3 2 1] => [5 6 7 4 3 2 1]

  • Reverse array[n-k,n]: [5 6 7 4 3 2 1] => [5 6 7 1 2 3 4]

  • Java:

(Rotate-Array.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class Solution {
    public void rotate(int[] nums, int k) {
            k = k%nums.length;
            rotate(nums,0,nums.length-1);
            rotate(nums,0,k-1);
            rotate(nums,k,nums.length-1);

        }

    public void rotate(int[] nums, int i, int j){
        while (i<j){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i ++;
            j--;
        }
    }
}
  • Python
(Rotate-Array.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution(object):
    def revert(self,nums,start,end):
        i = start
        j = end
        while i<j:
            nums[i],nums[j] = nums[j],nums[i]
            i += 1
            j -= 1

    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        k = k%len(nums)
        if k<0:
            return

        # reverse the whole array
        self.revert(nums,0,len(nums)-1)
        # reverse left k
        self.revert(nums,0,k-1)

        # reverse right n-k
        self.revert(nums,k,len(nums)-1)