# [LeetCode] 31. Next Permutation 下一个排列

2021年09月15日 阅读数：2

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.html

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).java

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

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.post

`1,2,3` → `1,3,2`
`3,2,1` → `1,2,3`
`1,1,5` → `1,5,1`url

Java:排序

```public void nextPermutation(int[] num) {
int n=num.length;
if(n<2)
return;
int index=n-1;
while(index>0){
if(num[index-1]<num[index])
break;
index--;
}
if(index==0){
reverseSort(num,0,n-1);
return;
}
else{
int val=num[index-1];
int j=n-1;
while(j>=index){
if(num[j]>val)
break;
j--;
}
swap(num,j,index-1);
reverseSort(num,index,n-1);
return;
}
}

public void swap(int[] num, int i, int j){
int temp=0;
temp=num[i];
num[i]=num[j];
num[j]=temp;
}

public void reverseSort(int[] num, int start, int end){
if(start>end)
return;
for(int i=start;i<=(end+start)/2;i++)
swap(num,i,start+end-i);
}　　```

Python:内存

```class Solution(object):
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
# find longest non-increasing suffix
right = len(nums)-1
while nums[right] <= nums[right-1] and right-1 >=0:
right -= 1
if right == 0:
return self.reverse(nums,0,len(nums)-1)
# find pivot
pivot = right-1
successor = 0
# find rightmost succesor
for i in range(len(nums)-1,pivot,-1):
if nums[i] > nums[pivot]:
successor = i
break
# swap pivot and successor
nums[pivot],nums[successor] = nums[successor],nums[pivot]
# reverse suffix
self.reverse(nums,pivot+1,len(nums)-1)

def reverse(self,nums,l,r):
while l < r:
nums[l],nums[r] = nums[r],nums[l]
l += 1
r -= 1　```

Python:

```class Solution:
def nextPermutation(self, num):
k, l = -1, 0
for i in xrange(len(num) - 1):
if num[i] < num[i + 1]:
k = i

if k == -1:
num.reverse()
return

for i in xrange(k + 1, len(num)):
if num[i] > num[k]:
l = i

num[k], num[l] = num[l], num[k]
num[k + 1:] = num[:k:-1]
```

C++：

```class Solution {
public:
void nextPermutation(vector<int> &num) {
int i, j, n = num.size();
for (i = n - 2; i >= 0; --i) {
if (num[i + 1] > num[i]) {
for (j = n - 1; j > i; --j) {
if (num[j] > num[i]) break;
}
swap(num[i], num[j]);
reverse(num.begin() + i + 1, num.end());
return;
}
}
reverse(num.begin(), num.end());
}
};
```

C++:

```class Solution {
public:
void nextPermutation(vector<int> &num) {
if(num.size()<2) return;
int n = num.size(), j = n-2;
while(j>=0 && num[j]>=num[j+1]) j--;

if(j<0) {
sort(num.begin(),num.end());
return;
}

int i=j+1;
while(i<n && num[i]>num[j]) i++;
i--;

swap(num[i],num[j]);
sort(num.begin()+j+1, num.end());
}
};```

[LeetCode] 46. Permutations 全排列

[LeetCode] 47. Permutations II 全排列 II

[LeetCode] 60. Permutation Sequence 序列排序