51.前の並び

1370 ワード

説明
配列を表して整数配列を指定し、前の配列を探します.
注意事項
配列には重複した整数が含まれています.
サンプル
[1,3,2,3]の順を示し、その前の配列は[1,2,3,3]の順を示し、[1,2,3,4]の順を示し、その前の配列は[4,3,2,1]である.
考え方http://blog.csdn.net/guoziqing506/article/details/51870732
コード
import java.util.ArrayList;

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers that's previous permuation
     */
    public void swapItem(ArrayList nums, int i, int j) {
        Integer tmp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, tmp);
    }
    
    public void swapList(ArrayList nums, int i, int j) {
        while (i < j) {
            swapItem(nums, i, j);
            i ++; 
            j --;
        }
    }
    
    public ArrayList previousPermuation(ArrayList nums) {
        int len = nums.size();
        if (len <= 1) {
            return nums;
        }
        int i = len - 1;
        while (i > 0 && nums.get(i) >= nums.get(i-1)) {
            i--;
        }
        swapList(nums, i, len - 1);     
        if (i != 0) {
            int j = i;
            while (nums.get(j) >= nums.get(i-1)) {
                j++;
            }
            swapItem(nums, j, i-1);
        }
        
        return nums;
    }
}