FilesExpand file tree

 master

/

rotate-array.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

50 lines (44 loc) · 1.53 KB

 master

/

rotate-array.py

Copy path

Top

File metadata and controls

• Code
• Blame

50 lines (44 loc) · 1.53 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

# Time: O(n)

# Space: O(1)

#

# 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.

#

class Solution:

# @param nums, a list of integer

# @param k, num of steps

# @return nothing, please modify the nums list in-place.

def rotate(self, nums, k):

k %= len(nums)

self.reverse(nums, 0, len(nums))

self.reverse(nums, 0, k)

self.reverse(nums, k, len(nums))

def reverse(self, nums, start, end):

while start < end:

nums[start], nums[end-1] = nums[end-1], nums[start]

start += 1

end -= 1

from fractions import gcd

class Solution2:

# @param nums, a list of integer

# @param k, num of steps

# @return nothing, please modify the nums list in-place.

def rotate(self, nums, k):

k %= len(nums)

num_cycles = gcd(len(nums), k)

cycle_len = len(nums) / num_cycles

for i in xrange(num_cycles):

self.apply_cycle_permutation(k, i, cycle_len, nums)

def apply_cycle_permutation(self, k, offset, cycle_len, nums):

tmp = nums[offset]

for i in xrange(1, cycle_len):

nums[(offset+i*k) % len(nums)], tmp = tmp, nums[(offset+i*k) % len(nums)]

nums[offset] = tmp

if __name__ == '__main__':

nums = [1,2,3,4,5,6,7]

Solution().rotate(nums, 3)

print nums