# lc31. Next Permutation

Contents

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for `arr = [1,2,3]`, the following are considered permutations of `arr`: `[1,2,3]`, `[1,3,2]`, `[3,1,2]`, `[2,3,1]`.

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of `arr = [1,2,3]` is `[1,3,2]`.
• Similarly, the next permutation of `arr = [2,3,1]` is `[3,1,2]`.
• While the next permutation of `arr = [3,2,1]` is `[1,2,3]` because `[3,2,1]` does not have a lexicographical larger rearrangement.

Given an array of integers `nums`, find the next permutation of `nums`.

The replacement must be in place and use only constant extra memory.

Example 1:

 ``````1 2 `````` ``````Input: nums = [1,2,3] Output: [1,3,2] ``````

Example 2:

 ``````1 2 `````` ``````Input: nums = [3,2,1] Output: [1,2,3] ``````

Example 3:

 ``````1 2 `````` ``````Input: nums = [1,1,5] Output: [1,5,1] ``````

Constraints:

• `1 <= nums.length <= 100`
• `0 <= nums[i] <= 100`
###### 解题思路

1. 对nums，从右边往左边扫，寻找nums[i-1]<nums[i]的情况
2. 如果无法找到（严格降序），那么返回严格升序序列
3. 如果可以找到，那么把num[i-1]和num[i: ~]中最小的数字交换，然后把num[i: ~]全部严格升序排列
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 `````` ``````class Solution(object): def nextPermutation(self, nums): """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """ for i in range(2,len(nums)+1): if nums[-i]nums[-i]: min_value=nums[-j] if nums[-j]<=min_value: min_idx=-j min_value=nums[-j] nums[-i],nums[min_idx]=nums[min_idx],nums[-i] nums[-i+1:]=sorted(nums[-i+1:],reverse=False) return nums[:]=sorted(nums,reverse=False) ``````

1. 题目中强调不需要return，而是直接在nums上修改，因此如果是新建内存空间再赋值给nums，有可能无法通过。
2. 记得最后如果是严格降序，需要返回严格升序。
3. 在剩下序列中找的最小值，一定要大于nums[i-1]