Previous Permuation(lintcode)

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.

解题思路

和前一题 Next Permutation 非常类似，这里找上一个排列，仍然使用字典序算法，大致步骤如下：

1. 从后往前寻找索引满足 a[k] > a[k + 1], 如果此条件不满足，则说明已遍历到最后一个。
2. 从后往前遍历，找到第一个比a[k]小的数a[l], 即a[k] > a[l].
3. 交换a[k]与a[l].
4. 反转k + 1 ~ n之间的元素。

public int[] previousPermuation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }

        // step1: find nums[i] > nums[i + 1]
        int i = 0;
        for (i = nums.length - 2; i >= 0; i--) {
            if (nums[i] > nums[i+1]) {
                break;
            } else if (i == 0) {
                // reverse nums if reach minimum
                reverse(nums, 0, nums.length - 1);
                return nums;
            }
        }

        // step2: find nums[i] > nums[j]
        int j = 0;
        for (j = nums.length - 1; j > i; j--) {
            if (nums[i] > nums[j]) {
                break;
            }
        }

        // step3: swap betwenn nums[i] and nums[j]
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;

        // step4: reverse between [i + 1, n - 1]
        reverse(nums, i + 1, nums.length - 1);

        return nums;
}

private void reverse(int[] nums, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}