题目
下一个排列
给定一个整数数组来表示排列,找出其之后的一个排列。
样例
给出排列[1,3,2,3]
,其下一个排列是[1,3,3,2]
给出排列[4,3,2,1]
,其下一个排列是[1,2,3,4]
注意
排列中可能包含重复的整数
解题
和上一题求上一个排列应该很类似
1.对这个数,先从右到左找到递增序列的前一个位置,peakInd
2.若peakInd = -1 这个数直接逆序就是答案了
3.peakInd>= 0 peakInd这个位置的所,和 peakInd 到nums.size() -1 内的数比较,返回 nums[peakInd] < nums[swapInd]最大的下标 swapInd
nums[swapInd] 是和nums[peakInd] 最接近并且比 nums[peakInd]大的数,这两个数进行交换
4.同样,peakInd + 1 到nums.length() - 1 内的数进行逆序
Python
class Solution:
# @param num : a list of integer
# @return : a list of integer
def nextPermutation(self, nums):
# write your code here
peakInd = len(nums) - 1
while peakInd>0 and nums[peakInd] <= nums[peakInd-1]:
peakInd -=1
peakInd -=1
if peakInd>=0:
swapInd = peakInd + 1
while swapInd< len(nums) and nums[swapInd]> nums[peakInd]:
swapInd +=1
swapInd -=1
nums[swapInd],nums[peakInd] = nums[peakInd],nums[swapInd]
left = peakInd + 1
right = len(nums) - 1
while left < right:
nums[left],nums[right] = nums[right],nums[left]
left +=1
right -=1
return nums
Python Code
Java
public class Solution {
/**
* @param nums: an array of integers
* @return: return nothing (void), do not return anything, modify nums in-place instead
*/
public int[] nextPermutation(int[] nums) {
// write your code here
int peakInd = nums.length-1;
while(peakInd>0 && nums[peakInd-1] >= nums[peakInd]){
peakInd --;
}
peakInd --;
if(peakInd>=0){
int swapInd = peakInd + 1;
while(swapInd< nums.length && nums[swapInd] > nums[peakInd]){
swapInd ++;
}
swapInd --;
swapnums(nums,peakInd,swapInd);
}
int left = peakInd + 1;
int right = nums.length - 1;
while(left< right){
swapnums(nums,left,right);
left +=1;
right -=1;
} return nums;
}
private void swapnums(int[] nums,int left,int right){
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
}
Java Code