Lintcode 51. Previous Permutation

Given a list of integers, which denote a permutation.

Find the previous permutation in ascending order.

Example

Example 1:

Input:[1]
Output:[1]

Example 2:

Input:[1,3,2,3]
Output:[1,2,3,3]

Example 3:

Input:[1,2,3,4]
Output:[4,3,2,1]

Notice

The list may contains duplicate integers.

Code (Java):

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: A list of integers that's previous permuation
     */
    public List<Integer> previousPermuation(List<Integer> nums) {
        // write your code here
        if (nums == null || nums.size() <= 1) {
            return nums;
        }

        Integer[] ans = new Integer[nums.size()];
        ans = nums.toArray(ans);
        // step 1: find the first ascending element
        int i = ans.length - 2;
        while (i >= 0 && ans[i] <= ans[i + 1]) {
            i--;
        }

        // step 2: find the largest element smaller than nums[i]
        if (i >= 0) {
            int j = i + 1;
            while (j < ans.length && ans[j] < ans[i]) {
                j++;
            }
            j--;
            swap(ans, i, j);
        }

        reverse(ans, i + 1);

        return Arrays.asList(ans);
    }

    private void swap(Integer[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(Integer[] nums, int start) {
        int end = nums.length - 1;
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}