LeetCode-中等-31-下一个排列(C)
题目
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
示例 4：
输入：nums = [1]
输出：[1]
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
- 这个题目可以先用个例子试一下，我用的是12345，一直往上排序。
- 如右边，从12345向上的十个例子。
- 多列几个来找规律：
- 这里原本想说下我找的过程，但过于繁琐了，直接说结论了。
- 从右边开始向左移动，数字将会呈现单调不减的趋势，直到碰到第一个拐点，变小的那个值，就是我们需要交换的第一个值。
- 这个值需要跟其右边，第一个大于它的数交换。
- 交换后，右边的顺序依然是从右往左从小到大排序，只需要将右边的数列颠倒，即可得出结果。
- 例如右边的(6)：
- 12543，可以看出，543是从右到左从小到大排序，而到2的时候，下降了，而大于2的第一个数，是3。
- 因此将2与3交换，得到13542，可以看出，右侧的542依然保持顺序，将其颠倒，得到13245，及下一个更大的数列。
- 再比如23541：
- 541保持顺序，到3变小，将1与3调换，得到21543，再将543颠倒，得到21345，即结果。
- 12345
- 12354
- 12435
- 12453
- 12534
- 12543
- 13245
- 13254
- 13425
- 13452
- 比如12344331：
- 44331保持顺序，到3变小，因为是从右往左寻找，因此找到第一个大于它的值，即4，交换，得到12443331。颠倒，得到12413334。
代码
void nextPermutation(int* nums, int numsSize){
int pos, temp, posRight;
/*
如果pos位置的值比pos-1的值大，那么比较pos后面的值，找到一个biggerPos，使得biggerPos的值是第一个大于pos-1的。
之后，将biggerPos和pos-1交换，并从小到大排序。
这里的从小到大排序不需要用算法，直接颠倒即可，因为必然是从小到大的顺序。
如果pos位置的值比pos-1小，那么继续pos--，继续比较。
这个算法是从最后往前，数字会递增，直到出现第一个变小的数字，将后面数中，所有大于它的数，取最小的那个。
这样交换后，还能保持上升后再下降的趋势。
*/
for(pos=numsSize-1; pos>0; pos--){
if(nums[pos-1]>=nums[pos]){
continue;
}
for(posRight=numsSize-1; posRight>=pos; posRight--){
if(nums[pos-1]<nums[posRight]){
break;
}
}
temp = nums[pos-1];
nums[pos-1] = nums[posRight];
nums[posRight] = temp;
break;
}
//颠倒算法，即排序算法。
for(posRight=0; posRight < (numsSize-pos)/2; posRight++){
temp = nums[pos+posRight];
nums[pos+posRight] = nums[numsSize-1-posRight];
nums[numsSize-1-posRight] = temp;
}
}
共有 0 条评论