LintCode - Previous Permutation

PreviousPermutation.java

public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {
	// write your code
	if(nums == null || nums.size() < 2) return nums;
	int start = -1;
	// find the fisrt "large" number
	for(int i=nums.size()-2; i>=0; i--){
	    if(nums.get(i) > nums.get(i+1)){
	        start = i;
	        break;
	    }
	}
    // if this "large" number exists, find the first smaller number
    if(start != -1){
        int index = nums.size() - 1;
        while(index > start){
		    if(nums.get(index) < nums.get(start)){
		        swap(nums, index, start);
		        break;
		    }
		    index--;
		}
    }
	// reverse the scanned part in the first round
	int left = start + 1, right = nums.size()-1;
	while(left < right){
	    swap(nums, left++, right--);
	}
	return nums;
}

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