实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
推导:
如何得到这样的排列顺序?这是本文的重点。我们可以这样来分析:
算法流程:
标准的“下一个排列”算法可以描述为:
class Solution {
public void nextPermutation(int[] nums) {
int len = nums.length;
if (len < 2) return;
int i = len - 2;
int j = len - 1;
int k = len - 1;
// 从后向前找第一个正序,这里最后i指向的是逆序起始位置
while (i >= 0 && nums[i] >= nums[j]) {
i--;
j--;
}
if (i >= 0) {
// 从后向前找第一个比nums[j]大的元素,进行交换
while (nums[i] >= nums[k]) {
k--;
}
swap(nums, i, k);
}
// 翻转交换点后的数组,使后面的数组升序,保证整个数组是下一个最大数组
reverse(nums, j, len - 1);
}
public void swap(int[] nums, int i, int j) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[end];
nums[end] = nums[start];
nums[start] = temp;
start++;
end--;
}
}
}