Next Permutation

Source

• leetcode: Next Permutation

Given a list of integers, which denote a permutation.

Find the next permutation in ascending order.

Example
For [1,3,2,3], the next permutation is [1,3,3,2]

For [4,3,2,1], the next permutation is [1,2,3,4]

Note
The list may contains duplicate integers.

Java

public class Solution {
    public void nextPermutation(int[] nums) {
        int cur = nums.length-1;
        while(cur>0 && nums[cur-1]>=nums[cur]) cur--;
        reverse(nums, cur, nums.length-1);

        int next = cur-1;
        if(next<0) return;
        while(cur<nums.length){
            if(nums[next]<nums[cur]){
                swap(nums, next, cur);
                return;
            }
            cur++;
        }
    }

    public void reverse(int[] nums, int left, int right){
        while(left<right){
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    public void swap(int[] nums, int left, int right){
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}