Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题目意思：给你一串数，要找到下一个排列，比这个排列大，并且恰好比这个排列大，就是说对于原排列和新排列没法找到另一个排列插在这二者之间。比如1,2,3，值是123，那么下一个排列就是132，你没法找到一个居于123和132之间的排列。

 

 

public class Solution {
    public void nextPermutation(int[] nums) {
    	if (nums == null || nums.length == 0) {
    		return ;
    	}
        int i = nums.length-2;
        while (i >= 0 && nums[i] >= nums[i+1]) {
        	i--;
        }
        if (i >= 0) {
        	int j = i + 1;
        	while (j < nums.length && nums[j] > nums[i]) {
        		j++;
        	}
        	j--;
        	swap(nums, i, j);
        }
        reverse(nums, i+1, nums.length-1);
    }

	private void reverse(int[] nums, int i, int j) {
		// TODO Auto-generated method stub
		while (i < j) {
			swap(nums, i,j);
			i++;
			j--;
		}
	}

	private void swap(int[] nums, int i, int j) {
		// TODO Auto-generated method stub
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}
}