FilesExpand file tree

 master

/

rotate_array.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

58 lines (49 loc) · 1.24 KB

 master

/

rotate_array.py

Copy path

Top

File metadata and controls

• Code
• Blame

58 lines (49 loc) · 1.24 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

51

52

53

54

55

56

57

58

"""

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.

"""

#

# Rotate the entire array 'k' times

# T(n)- O(nk)

#

def rotate_one_by_one(nums, k):

"""

:type nums: List[int]

:type k: int

:rtype: void Do not return anything, modify nums in-place instead.

"""

n = len(nums)

for i in range(k):

temp = nums[n-1]

for j in range(n-1, 0, -1):

nums[j] = nums[j-1]

nums[0] = temp

#

# Reverse segments of the array, followed by the entire array

# T(n)- O(n)

#

def rotate(nums, k):

"""

:type nums: List[int]

:type k: int

:rtype: void Do not return anything, modify nums in-place instead.

"""

n = len(nums)

k = k % n

reverse(nums, 0, n - k - 1)

reverse(nums, n - k, n - 1)

reverse(nums, 0, n - 1)

def reverse(array, a, b):

while a < b:

array[a], array[b] = array[b], array[a]

a += 1

b -= 1

def rotate_array(array, k):

if array is None:

return None

length = len(array)

return array[length - k:] + array[:length - k]