下一个排列
题目链接
读懂题目
要理解题目的意思，主要是要读懂这一句：整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。
我们来逐词分析：
其整数，即我们要将这个数组的数字构成一个十进制整数，例如数组[1,2,3]看成数字就是123，数组[4,0,3,2,1]看成数字就是40321下一个字典序更大：即我们要通过改变数组中的元素位置，从而使组成的整数大于原来的整数，并且变化幅度尽可能小。例如数组[1,2,3]的下一个排列就是[1,3,2]（132大于123，且相较于由1，2，3组成的更大的数字变化幅度最小）
还有一个例外情况：如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）
- 例如数组
[3,2,1]，构成的整数321已经是这三个数据所能构成的最大整数，因此它的下一个排列就是这三个数字的升序排列[1,2,3]
思路
我们以数组[4,5,2,6,3,1]为例，来讨论如何找到它的下一个排列：
- 首先我们应该清楚，下标越小的数字，组成数据时位数越高，因此寻找下一个排列时尽量不要动前面的数字，即应该从低位数据开始考虑
- 我们看到，后面的数字
631已经是逆序排序，即[6,3,1]这三个数字组成的最大数字，因此我们不能仅仅通过改变这三个数的位置来找到下一个排列
- 因此我们要继续向前看：到了数字
2，我们发现**[2,6,3,1]不是逆序排序了**，即我们可以通过改变[2,6,3,1]这四个数的位置来找到到下一个排列，即次大数。那么具体的，该怎么改变才能保证改变后的数比之前的数大，并且变化幅度最小呢？ - 由于
[6,3,1]已经是降序排序，因此我们必须要增大更高位的数字2，而为了使变化幅度最小，我们应该将数字2, 3交换位置，并且使交换完后3后的数据为升序排序。
- 最后，就得到了下一个排列
[4,5,3,1,2,6]
总的来说就是：
我们需要将一个左边的
较小数与一个右边较大数交换，以能够让当前排列变大，从而得到下一个排列。同时我们要让这个
较小数尽量靠右，而较大数尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。
我们可以这样描述我们的算法:
- 从后向前遍历数组元素,直到出现**
nums[i] < nums[i+1]这样,较小数min就是nums[i]**- 再从后往前遍历数组元素,直到出现**
nums[j] > min,这样较大数max就是nums[j]**- 交换
较小数min和较大数max的位置,这样就得到了更大的数- 将
较大数max后的数据转换为升序排序,这样就可以使变化幅度最小,即得到下一个排列
注意:
- 如果整个数组已经是降序排序,那么就不存在更大的数,难么他的下一个排列就是组成这个数组数据的升序排序. 而将降序转升序不需要采用时间复杂度较高的排序算法, 直接将整个数组反转即可, 时间复杂度为O(N)
- 将
较大数和较小数交换后, 将较大数后的数转为升序同理.
实现代码
//实现[left, right]区域数据的反转
void Reverse(int* nums, int left, int right)
{
while (left <= right)
{
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
//交换数据
void Swap(int *num1, int *num2)
{
int temp = *num1;
*num1 = *num2;
*num2 = temp;
}
void nextPermutation(int* nums, int numsSize){
//先找到 较小数
int min;
for (min = numsSize - 2; min >= 0; min--)
{
if (nums[min] < nums[min + 1])
break;
}
//如果较小数不存在,那么直接将数组反转即可
if (min < 0)
{
Reverse(nums, 0, numsSize - 1);
return;
}
//找较大数
int max;
for (max = numsSize - 1; max > min; max--)
{
if (nums[max] > nums[min])
break;
}
//交换较小数和较大数
Swap(&nums[min], &nums[max]);
//反转较大数后的数据
Reverse(nums, min + 1, numsSize - 1);
}
