FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
LeetCode-Solutions/Python/rotate-array.py at master · tehsints/LeetCode-Solutions · GitHub
tehsints
/
LeetCode-Solutions
Public
forked from
kamyu104/LeetCode-Solutions
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
LeetCode-Solutions
/
Python
/
rotate-array.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
105 lines (87 loc) · 2.52 KB
Breadcrumbs
LeetCode-Solutions
/
Python
/
rotate-array.py
Copy path
File metadata and controls
105 lines (87 loc) · 2.52 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
# Time: O(n)
# Space: O(1)
class
Solution
(
object
):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
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
# Time: O(n)
# Space: O(1)
from
fractions
import
gcd
class
Solution2
(
object
):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
def
rotate
(
self
,
nums
,
k
):
def
apply_cycle_permutation
(
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
k
%=
len
(
nums
)
num_cycles
=
gcd
(
len
(
nums
),
k
)
cycle_len
=
len
(
nums
)
/
num_cycles
for
i
in
xrange
(
num_cycles
):
apply_cycle_permutation
(
k
,
i
,
cycle_len
,
nums
)
# Time: O(n)
# Space: O(1)
class
Solution3
(
object
):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
def
rotate
(
self
,
nums
,
k
):
count
=
0
start
=
0
while
count
<
len
(
nums
):
curr
=
start
prev
=
nums
[
curr
]
while
True
:
idx
=
(
curr
+
k
)
%
len
(
nums
)
nums
[
idx
],
prev
=
prev
,
nums
[
idx
]
curr
=
idx
count
+=
1
if
start
==
curr
:
break
start
+=
1
# Time: O(n)
# Space: O(n)
class
Solution4
(
object
):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
def
rotate
(
self
,
nums
,
k
):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
nums
[:]
=
nums
[
len
(
nums
)
-
k
:]
+
nums
[:
len
(
nums
)
-
k
]
# Time: O(k * n)
# Space: O(1)
class
Solution5
(
object
):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
def
rotate
(
self
,
nums
,
k
):
while
k
>
0
:
nums
.
insert
(
0
,
nums
.
pop
())
k
-=
1
Back
|
FazBrowse Home
|
New Git URL