题目
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。1,2,3
→ 1,3,2
3,2,1
→ 1,2,3
1,1,5
→ 1,5,1
方案一(leetcode)
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
思路:
1、从后往前寻找第一个升序对 (i,j) 即 nums[i] < nums[j]
2、再从后往前找第一个大于 nums[i] 的数即为大数,并交换着两个元素即将大数换到前面
3、将大数后面的部分倒序
"""
n = len(nums)
if n<2: return nums
i = n-1
while i>0 and nums[i-1]>=nums[i]:#要是前者大于等于后者 则不是要调整的目标 继续前移
i -= 1
if i==0 and nums[i]==max(nums): #此数为最大数
return nums.reverse()
else: # 151 i=1
j = n-1
while j>i-1 and nums[j]<=nums[i-1]:
j -= 1
temp = nums[i-1] #i-1为小数 j为大数 交换之
nums[i-1] = nums[j]
nums[j] = temp
re = nums[i:]
for h in range (len(re)):
nums[n-1-h] = re[h]
return nums
方案二(leetcode)
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
for i in range(len(nums)-1, 0, -1):
if nums[i] > nums[i-1]:
tem_num = nums[i:]
tem_num.sort()
nums[i:] = tem_num
for j in range(i, len(nums)):
if nums[j] > nums[i-1]:
nums[j], nums[i-1] = nums[i-1], nums[j]
break
return
nums.sort()
参考链接
https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/280/array/1249/
https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/