算法——LeetCode31. 下一个排列
31. 下一个排列
题目：下一个排列
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
题解1：
核心: 从后往前找相邻两个为升序的元素, 小大 主要思路流程：
- 从后往前找相邻元素为升序的两个数，a[i],a[j],这时我们要替换的一个数为a[i],j之后的序列必为降序
- 寻找要与a[i] 替换的另一个数，即要找到一个最小的比a[i]大的数， 由于j后面都是降序，从后往前找的第一个比a[i]大的数就是最小的数，设为a[k]
- 交换a[i]与a[k]的值
- 此时下标 i 后面的数都按降序排列，由于是找比当前排列大的最小排列，所以将 i 后的数变为最小排列即可，做法就是逆置 i 之后的数。
- 如果当前排列为最大排列，那么直接逆置整个排列即为结果。（代码中通过前面j是否为0来判断，若为0，说明未搜索到相邻升序元素）
注意点:
-
从后往前找升序的两元素, 小大 循环判断中要 break 最后排序的下标为 (top, nums.length)
以下两种代码思想相同, 写法略不同 代码1(使用数组排序函数):
class Solution {
public void nextPermutation(int[] nums) {
int replace = 0, top = 0;// replace 记录要交换的元素, top 相当于一个小峰值
for (int i = nums.length - 1; i > 0; i--) {
if (nums[i] > nums[i - 1]) {
replace = i - 1;
top = i;
break;
}
}
for (int i = nums.length - 1; i > replace; i--) {
if (nums[i] > nums[replace]) {
int temp = nums[replace];
nums[replace] = nums[i];
nums[i] = temp;
break;
}
}
if (top == 0) {
// 若 top 为初始值 0 , 说明为最大排列, 直接从小到大排序数组
Arrays.sort(nums);
} else {
Arrays.sort(nums, top, nums.length);
}
}
}
代码2：
class Solution {
public void nextPermutation(int[] nums) {
int i = 0, j = 0, k;
//找到第一个相邻升序的下标
for (int p = nums.length - 1; p >= 1; p--) {
if (nums[p - 1] < nums[p]) {
i = p - 1;
j = p;
break;//找到第一个就要退出
}
}
//从i之后找到第二个要被替换的数
for (int q = nums.length - 1; q > i; q--) {
if (nums[i] < nums[q]) {
k = q;
swap(nums, i, k);//交换两个数
break;//交换后退出
}
}
if (j == 0) {
//若搜索到升序序列，j最小为1，此时说明交换数组为最大排列，逆置序列即可
reverse(nums, 0, nums.length - 1);
} else {
//前面进行了交换，将 i 之后的数逆置排列
reverse(nums, i + 1, nums.length - 1);
}
}
//交换数组指定位置的值
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
//逆置指定下标后的元素
public void reverse(int[] a, int i, int j) {
while (i < j && i != j) {
swap(a, i, j);
i++;
j--;
}
}
}
-
参考题解：