LeetCode 题解31：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.从数组的尾端开始向前遍历，找到递减序列data[i]~data[n-1]

2.从这个递减序列中找出一个比data[i - 1]大的值（从尾端开始找）

3.交换这两个值，并且把data[i]到data[n-1]进行排序（从小到大） ***

代码如下

public void nextPermutation(int[] nums) {
    
    if ( null == nums || nums.length < 2 )
		 return;
	 
	 
	 // 先找到最右边第一个递减序列
	 int index = nums.length - 1;
	 for (; index > 0 && nums[index - 1] >= nums[index]; index--){}
	 

	// 整个数组已经是递减排序了，变成最小的组合，甚至直接返回也可以	 
	 if ( index == 0 ) {
		 for (int i = 0; i < nums.length / 2; i++) {
			 int temp = nums[i];
			 nums[i] = nums[ nums.length - 1 - i ];
			 nums[ nums.length - 1 - i ] = temp;
		 }
		 return;
	 }
	 

	 int min_index = nums.length - 1;
	 for (; min_index >= 0 && nums[min_index] <= nums[index - 1]; min_index--) {}
	 
	 int temp = nums[index - 1];
	 nums[index - 1] = nums[min_index];
	 nums[min_index] = temp;
	 
	 
	 Arrays.sort(nums, index, nums.length);
    
}

Written on April 17, 2016