题目

给定一个整数数组来表示排列，找出其之后的一个排列。

样例

给出排列[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

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;        }}