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.
Example 1:
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
题目翻译
实现“下一个排列”函数，将排列中的数字重新排列成字典序中的下一个更大的排列。
如果这样的重新排列是不可能的，它必须重新排列为可能的最低顺序（即升序排序）。
重排必须在原地，不分配额外的内存。
示例1：
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
解题方案
标签： Array
思路：
首先肯定从后面开始看，1和5调换了没有用。
7、5和1调换了也没有效果，因此而发现了8、7、5、1是递减的。
如果想要找到下一个排列，找到递增的位置是关键。
因为在这里才可以使其增长得更大。
于是找到了4，显而易见4过了是5而不是8或者7更不是1。
因此就需要找出比4大但在这些大数里面最小的值，并将其两者调换。
那么整个排列就成了：6 5 5 8 7 4 1
然而最后一步将后面的8 7 4 1做一个递增。
代码：
public void nextPermutation(int[] nums) {
int index = nums.length - 1;
while (index > 0 && nums[index] <= nums[index - 1]) {
--index;
}
if (index == 0) {
Arrays.sort(nums);
return;
}
int second = Integer.MAX_VALUE, secondIndex = Integer.MAX_VALUE;
for (int i = nums.length - 1; i >= index - 1; --i) {
if (nums[i] > nums[index - 1] && nums[i] < second) {
second = nums[i];
secondIndex = i;
}
}
int tmp = nums[index - 1];
nums[index - 1] = nums[secondIndex];
nums[secondIndex] = tmp;
Arrays.sort(nums, index, nums.length);
}