题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

来源，leetcode 每日一题 31. 下一个排列

解题思路

从右边往左，找到第一个下降的数字，然后从右边中找到比它大且最接近它的数字，进行替换，然后将其右侧按照升序排列即可。

代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int flag = 0;
        int last = nums[nums.size() - 1];
        vector<int>:: iterator it;
        for (it = nums.end() - 1; it >= nums.begin(); it--) {
            if (*it >= last) {
                last = *it;
            }  else {
                for (vector<int>:: iterator it2 = nums.end() - 1; it2 != it; it2--) {
                    if (*it2 > *it) {
                        int temp  = *it2;
                        *it2 = *it;
                        *it = temp;
                        break;
                    }
                }
                break;
            }
        }
        it++;
        sort(it, nums.end());
    }
};