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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

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