Python-LeetCode 189 Rotate Array

LeetCode 189 Rotate Array

Exchange blogroll: http://laker.me/blog
Github:https://github.com/younglaker

Description

https://leetcode.com/problems/rotate-array/

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

Example 1:

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]

Example 2:

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]

Note:

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?

Solution one

Expalnation:

Expalnation

Every element moves k steps and it will get the correct array.

Method one

Use a new list to store the result, but it need O(n) space.

Method two

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[0]->nums[2]->nums[4]->nums[0], so we have to move to nums[1] 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’

Full Code in Github :

https://github.com/younglaker/leetcode/blob/master/189_Rotate_Array.py

Code explanation

Code explanation

Solution two

Expalnation:

Expalnation

  • Reverse the whole list
  • Reverse list from 0 to k-1 (because the list starts from 0)
  • Reverse list from k to length-1

Full Code in Github :

https://github.com/younglaker/leetcode/blob/master/189_Rotate_Array2.py

Code explanation

Code explanation


Python-LeetCode 189 Rotate Array

本文原创自http://laker.me/blog,转载请注明出处,欢迎交换友链

如果本文对您有帮助,微信扫一扫,请我吃个鸡腿吧