给定一个整数数组来表示排列，找出其之后的一个排列。
注意事项
排列中可能包含重复的整数
样例
给出排列[1,3,2,3]，其下一个排列是[1,3,3,2]
给出排列[4,3,2,1]，其下一个排列是[1,2,3,4]
思路：
和 下一个排列II 一个思路一样，细节上的区别
代码
- version1
public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers that's next permuation
*/
public void swapItem(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void swapList(int[] nums, int i, int j) {
while (i < j) {
swapItem(nums, i, j);
i ++;
j --;
}
}
public int[] nextPermutation(int[] nums) {
int len = nums.length;
if (len <= 1) {
return nums;
}
int i = len - 1;
// 找到那个满足 nums[i] > nums[i - 1] 的 i，i - 1 是需要交换的位置
while (i > 0 && nums[i] <= nums[i - 1]) {
i--;
}
swapList(nums, i, len - 1);
// 找到那个比 nums[i - 1] 大的数中最接近 nums[i - 1] 的数
if (i != 0) {
int j = i;
while (nums[j] <= nums[i - 1]) {
j++;
}
swapItem(nums, j, i-1);
}
return nums;
}
}
- version 2
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 int[] nextPermutation(int[] num) {
// find the last increase index
int index = -1;
// 注意此处 i 别越界
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 num;
}
// find the first bigger one
int biggerIndex = index + 1;
// 寻找 biggerIndex 的顺序很重要，从右往左开始是依次递增的顺序
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);
return num;
}
}
细节上需要注意的是寻找 index 和 biggerIndex 的两个for循环不能忘记加break
