描述
给定一个若干整数的排列，给出按正数大小进行字典序从小到大排序后的下一个排列。
如果没有下一个排列，则输出字典序最小的序列。
样例
左边是原始排列，右边是对应的下一个排列。
1,2,3→1,3,2
3,2,1→1,2,3
1,1,5→1,5,1
挑战
不允许使用额外的空间
思路
字典序原理
代码
public class Solution {
/**
* @param num: an array of integers
* @return: return nothing (void), do not return anything, modify num in-place instead
*/
public void reverse(int[] num, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
int temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
public void nextPermutation(int[] num) {
// find the last increase index
int index = -1;
for (int i = num.length - 2; i >= 0; i--) {
if (num[i] < num[i + 1]) {
index = i;
break;
}
}
// 特殊情况，当前序列为最后一个序列
if (index == -1) {
reverse(num, 0, num.length - 1);
return;
}
// find the first bigger one
int biggerIndex = index + 1;
for (int i = num.length - 1; i > index; i--) {
if (num[i] > num[index]) {
biggerIndex = i;
break;
}
}
// swap them to make the permutation bigger
int temp = num[index];
num[index] = num[biggerIndex];
num[biggerIndex] = temp;
// reverse the last part
reverse(num, index + 1, num.length - 1);
}
}
