-
Notifications
You must be signed in to change notification settings - Fork 0
/
P031_NextPermutation.py
59 lines (52 loc) · 1.44 KB
/
P031_NextPermutation.py
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
#coding=utf-8
'''
url: leetcode.com/problems/next-permutation/
@author: zxwtry
@email: zxwtry@qq.com
@date: 2017年4月1日
@details: Solution: 95ms 11.05%
'''
class Solution(object):
#[i, j)
def decreaseFirstLarger(self, n, i, j, v):
j -= 1
while i < j:
m = (i + j + 1) // 2
if n[m] > v:
i = m
else:
j = m - 1
return j
def swap(self, n, i, j):
t = n[i]
n[i] = n[j]
n[j] = t
#[i, j)
def reverse(self, n, i, j):
j -= 1
while i < j:
self.swap(n, i, j)
i += 1
j -= 1
def nextPermutation(self, n):
"""
:type n: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
nn = 0 if n == None else len(n)
#return short n
if nn < 2: return
#find decrease sub list [i, nn - 1]
i = nn - 1
while i > 0 and n[i - 1] >= n[i]:
i -= 1
#[0, nn - 1] is decrease sub list
if i == 0:
n.reverse()
return
self.swap(n, i - 1, self.decreaseFirstLarger(n, i, nn, n[i - 1]))
self.reverse(n, i, nn)
if __name__ == "__main__":
n = [2, 5, 1, 1]
Solution().nextPermutation(n)
print(" %d" * len(n) % tuple(n))