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,即结果。
  1. 12345
  2. 12354
  3. 12435
  4. 12453
  5. 12534
  6. 12543
  7. 13245
  8. 13254
  9. 13425
  10. 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;
    }

}

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注