下一个排列(数组推导）

题目描述

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。

示例 1：

输入：nums = [1,2,3]

输出：[1,3,2]

示例 2：

输入：nums = [3,2,1]

输出：[1,2,3]

示例 3：

输入：nums = [1,1,5]

输出：[1,5,1]

链接：https://leetcode-cn.com/problems/next-permutation

解题思路

1.首先数组中从后往前寻找，升序排列的第一个位置i,使得nums[i] <nums[i+1]

2.在[1+1,n]中寻找一个最小的输nums[j]使得nums[j]大于nums[i]

3.交换nums[i]与nums[j]的位置，然后翻转子数组[i+1,n]

代码实现

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        bool isFind = false;
        int n = nums.size();
        int i = n - 2;
        //寻找升序排列的第一个位置i,使得nums[i] <nums[i+1]
        for(; i >= 0; i--){
            if(nums[i] < nums[i + 1]){
                isFind = true;
                break;
            }
                
        } 
        //在[1+1,n]中寻找一个最小的输nums[j]使得nums[j]大于nums[i]
        if(isFind){
            int k = i + 1;
            for(int j = i + 1; j < n; j ++){
                if(nums[j] > nums[i] && nums[j] <= nums[k]){
                        k = j;
                }
            }  
            swap(nums[i], nums[k]); 
        }
        else{
            i = -1;
        }   
        //翻转子数组[i+1,n]    
        int mid = (n - i)/2;
        for(int k = 1; k <= mid; k ++){
            swap(nums[i + k], nums[n - k]);
        }
    }
};