Previous Permutation

http://www.lintcode.com/en/problem/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]

Thoughts

把next permutation的比大小符号都反过来.

Code

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
        int i;
        int n = nums.size();
        for (i = n - 1; i > 0; i--) {
            if (nums.get(i - 1) > nums.get(i)) {
                break;
            }
        }

        i--;
        if (i >= 0) {
            for (int j = n - 1; j > i; j--) {
                if (nums.get(j) < nums.get(i)) {
                    swap(nums, i, j);
                    break;
                }
            }
        }

        reverse(nums, i + 1, n - 1);
        return nums;
    }

    public void reverse(List<Integer> nums, int start, int end) {
        while (start < end) {
            swap(nums, start++, end--);
        }
    }

    public void swap(List<Integer> nums, int i, int j) {
        int tmp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, tmp);
    }
}

Analysis

时间复杂度O(N).