Previous Permutation 51

Question

Given a list of integers, which denote a permutation.

Find the previous permutation in ascending order.

Notice

The list may contains duplicate integers.

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]

Solution

这题就是next permutation的逆过程。首先找到从后往前遍历，直到找到一个数（假设位置为i）比之它前一位数小（即该位到数组的最后是一个递增序列），然后将i到数组最后的所有数按递减排列。然后在这个递增数列里面找到第一个比i－1位置上数小的数，交换两个数的位置即可。如果i＝1则说明之前的整个数组都是递增序列，现在整个数组变为递减数列，正好是previous permutation，因此不用再做任何其他操作。

代码如下：

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) {
        // write your code
        if(nums == null || nums.size() == 0){
            return nums;
        }

        int length = nums.size();
        int i = length - 1;
        while(i > 0 && nums.get(i) >= nums.get(i - 1)){
            i--;
        }
        swapList(nums, i, length - 1);

        if(i != 0){
            int j = i;
            while(nums.get(i - 1) <= nums.get(j)){
                j++;
            }
            swapItem(nums, i - 1, j);
        }

        return nums;
    }

    private void swapList(ArrayList<Integer> nums, int start, int end){
        while(start < end){
            swapItem(nums, start, end);
            start++;
            end--;
        }
    }

    private void swapItem(ArrayList<Integer> nums, int i, int j){
        int temp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, temp);
    }
}