LeetCode 31. 下一个排列
31. 下一个排列
题目：整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 给你一个整数数组 nums ，找出 nums 的下一个排列。 必须 原地 修改，只允许使用额外常数空间。 (题意不是很明确，具体看链接，看不懂可以看评论) 链接
官方思路
注意 如果在步骤 1 找不到顺序对，说明当前序列已经是一个降序序列，即最大的序列，我们直接跳过步骤 2 执行步骤 3，即可得到最小的升序序列。 该方法支持序列中存在重复元素，且在 C++ 的标准库函数 next_permutation 中被采用。
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = len(nums) - 1
while j >= 0 and nums[i] >= nums[j]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
复杂度分析 时间复杂度：O(N)，其中 N 为给定序列的长度。我们至多只需要扫描两次序列，以及进行一次反转操作。 空间复杂度：O(1)，只需要常数的空间存放若干变量。
上一篇：
92天倒计时，蓝桥杯省赛备赛攻略来啦~
下一篇：
一位腾讯在职7年测试工程师的心声...