[LintCode] 51 Previous Permutation 解题报告

Description
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]

思路
和Next Permutation这题的思路一模一样，代码几乎也一模一样。
唯一的区别是，先找第一个nums[i] > nums[i + 1]的i
再找从end到i之间第一个nums[j] < nums[i]的j.
只要改两个比较符就可以了。



Code

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
        int i = nums.size() - 2;
        while (i >= 0 && nums.get(i + 1) >= nums.get(i)) {
            i--;
        }
        if (i >= 0 ) {
            int j = nums.size() - 1;
            while (j >= 0 && nums.get(j) >= nums.get(i)) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1, nums.size() - 1);
        return nums;
    }
    
    public void swap(ArrayList<Integer> nums, int i, int j) {
        int tmp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, tmp);
    }
    
    public void reverse(ArrayList<Integer> nums, int i, int j) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }
}