31. 下一个排列
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
思路
这个题目主要是观察, 找出当前排列到下一个排列前后的变化
-
分为三种情况考虑:
- 列表长度小于等于1
- 不存在更大序列, 即列表为降序排序
- 存在更大序列:
- 从右往左遍历, 找到第一个谷底的点
- 找到谷底点后, 再从谷底的点开始往右遍历, 找到刚好比谷底点大的那个点
- 交换两个点位置
-
再将谷底点右侧的点按升序排列(这样值最小)
列表[1, 5, 8, 4, 7, 6, 5, 3, 1]的折线图
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 第一种情况, 啥也不用干
if len(nums) <= 1:
return
# 第二种情况, 从右往左遍历列表
for i in range(len(nums)-1, 0, -1):
# 如果当前点是谷底点
if nums[i] > nums[i-1]:
temp_i = i
# 从谷底点开始从左往右找
for j in range(i, len(nums)):
# 先比较是否比谷底的点大
if nums[j] > nums[i-1]:
# 再比较是否是更小的那个点, 来找到那个刚好大于谷底点的点
if nums[temp_i] > nums[j]:
temp_i = j
# 交换两个点位置
nums[i-1], nums[temp_i] = nums[temp_i], nums[i-1]
temp = nums[i:]
temp.sort()
nums[i:] = temp
return
# 第三种情况, 直接按升序排列
nums.sort()
