首页 LeetCode

31. 下一个排列

发布时间:2020年11月10日评论数：抢沙发阅读数：168

url:https://leetcode-cn.com/problems/next-permutation/

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

通过次数110,253

解题思路：

下一个更大的排序首先要更大比如 132>123 因此我们只需要将后面的大数和前面的小数交换位置即可

比如这里就是2和3交换了下

然后是下一个说明不能随便交换要保证是下一个也就是最临近的比如123可以排序为321、312、213、231都比123大

而最近的肯定是132这里我们就要从数字最后一位开始往前找，找到一个大于自己前一位的就开始做交换

然后把后面的全部从小到大排序即可，比如157643下一个就是163457过程就是从最后一位开始也就是3开始往前找找到一位

他的前面一位要小于它，就会找到7,7的前面是5是小于它

然后从找到的这位7开始，后面一串中找到大于5的最小数，也就是6，将6和5交换就变成了167543

然后把i后面的数字从小到大排序，其实可以发现后面 7543 已经是个从大到小的排序了，因此从i+1开始往后（也就是7）和从最后开始往前两两交换即可

有个极限条件就是本身就是最大序列比如321那么也就是从最后一位找到最开始都没找到前一位比它小的，那么就直接从小到大全排序即可

void nextPermutation(int* nums, int numsSize){
    for(int i=numsSize-1;i>0;i--){ //没找到，说明本身是最大排序
        if(i==1&&nums[i]<nums[i-1]){
            i--;
            while(i<numsSize/2){
                nums[i] = nums[i] + nums[numsSize-1-i];
                nums[numsSize-1-i] = nums[i] - nums[numsSize-1-i];
                nums[i] = nums[i] - nums[numsSize-1-i];
                i++;
            }
            break;
        }
        if(nums[i]>nums[i-1]){ //往前找找到前面一位小于
            i--; //找到后把前面一位标记为i
            for(int j=numsSize-1;j>=i;j--){ 
                if(nums[j]>nums[i]){//找后面大于i的最小数，和i交换
                nums[i] = nums[i] + nums[j];
                nums[j] = nums[i] - nums[j];
                nums[i] = nums[i] - nums[j];
                break; 
                }
            }
            i++;
            for(int j=0;j<(numsSize-i)/2;j++){ //从i开始交换排序，把从大到小变成从小到大
                nums[i+j] = nums[i+j] + nums[numsSize-1-j];
                nums[numsSize-j-1] = nums[i+j] - nums[numsSize-j-1];
                nums[i+j] = nums[i+j] - nums[numsSize-j-1];
            }
            break;
        }
    }
}