Given an array, rotate the array to the right by k steps, where k is non-negative.
Input: [1,2,3,4,5,6,7] and 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]
Input: [-1,-100,3,99] and 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]
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?
Every element moves k steps and it will get the correct array.
Use a new list to store the result, but it need O(n) space.
Set the element to the correct position one by one, it only need O(1) space and O(n) time.
Whewn the length of nums id odd, it can set to the correct position one by one for one time,
But when the lenght of nums is even, like the example above, it will collide. In our example above, the length of nums is 6 and when k=2, nums->nums->nums->nums, so we have to move to nums to restart. So in our code, when ‘i==j’, then ‘i++’.
Also the exchange will execute ‘length’ times. So in our code, it will exchange when ‘count < length’
- Reverse the whole list
- Reverse list from 0 to k-1 (because the list starts from 0)
- Reverse list from k to length-1