Previous Permutation

Source

• lintcode: Previous Permutation

Given a list of integers, which denote a permutation.

Find the previous permutation in ascending order.

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

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

Note
The list may contains duplicate integers.

Java

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers that's previous permuation
     */
    public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {
        int cur = nums.size()-1;
        while(cur>0 && nums.get(cur-1)<=nums.get(cur)) cur--;
        reverse(nums, cur, nums.size()-1);

        int next = cur-1;
        if(next<0) return nums;
        while(cur<nums.size()){
            if(nums.get(next)>nums.get(cur)){
                swap(nums, next, cur);
                return nums;
            }
            cur++;
        }
        return nums;
    }

    public void reverse(ArrayList<Integer> nums, int left, int right){
        while(left<right){
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    public void swap(ArrayList<Integer> nums, int left, int right){
        int tmp = nums.get(left);
        nums.set(left, nums.get(right));
        nums.set(right, tmp);
    }
}