[leetcode]031-Next Permutation[数学逻辑][python]

本文主要是介绍[leetcode]031-Next Permutation[数学逻辑][python]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 原题

https://leetcode.com/problems/next-permutation/

2. 思路

题意：求出给定序列的下一个序列。

思路：首先要理解什么是元素的全排列。一组数的全排列有多个方法获得。

题目要求的是字典序的排列组合。对于字典序的排列，两个相邻的排列要求前缀尽可能多。

所以下一个排列如何求呢？ 其实全排列过程是从后向前逆序的过程。

于是，我们从后向前找下标i-1元素小于后一个元素，然后再从i以后的元素找出比其大的最小元素。

交换后，对i以后的元素升序即是所求序列。

当然，边界情况：序列已经逆序，那么下一个就是升序序列。

3. 源码

class Solution:def nextPermutation(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""x,y = -1, -1for i in range(len(nums)-1, 0, -1):if nums[i-1] < nums[i] :  #从后找到第一个小的x = i-1breakif x == -1 : #列表逆序，下一个排列是升序nums.sort()else:for i in range(x+1, len(nums)): #找到比x大且最小的if (nums[i] > nums[x]):y = ielse:break;nums[x], nums[y] = nums[y], nums[x]nums[x+1:] = reversed(nums[x+1:])

 

这篇关于[leetcode]031-Next Permutation[数学逻辑][python]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---