-
Notifications
You must be signed in to change notification settings - Fork 0
/
31. Next Permutation.py
48 lines (48 loc) · 1.92 KB
/
31. Next Permutation.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
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# recent attempt, time O(N), space O(N)
if len(nums) <= 1:
return nums
idx = len(nums)-2
while idx>=0 and nums[idx] >= nums[idx+1]:
idx -= 1
if idx < 0:
nums.reverse()
return
swap_idx = idx+1
while swap_idx < len(nums) and nums[swap_idx] > nums[idx]:
swap_idx += 1
swap_idx -= 1
nums[idx], nums[swap_idx] = nums[swap_idx], nums[idx]
# nums[idx+1:]=nums[idx+1:][::-1] # can be further optimized to achieve O(1) space
left, right = idx+1, len(nums)-1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums
# #Time O(N), space O(N)
# #Modified Jake's solution for 556. Next Greater Element III
# n = len(nums)
# if n == 1: return nums
# # get index of first digit from right smaller than predecessor, return -1 if none
# j = -2
# while j > -n-1 and nums[j] >= nums[j+1]:
# j -= 1
# if j == -n-1:
# nums.reverse()
# else:
# # get index of first digit from right larger than digits[j]
# i = -1
# while nums[j] >= nums[i]:
# i -= 1
# ## swap digits at i and j
# nums[i],nums[j] = nums[j],nums[i]
# # Sort the remaining digits in ascedning order
# if j < -1:
# nums[j+1:] = nums[j+1:][::-1]