写在前面：

作为一个编程小白打算通过LeetCode刷题自学C++，特此不定期记录整理解题思路。

题目一：

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

示例:
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation

第一次尝试：

思路：最开始的思路就是根据数据排列组合，再按从小到大字典排序方式形成数据集，检索其中输入数值的下一个数返回。很显然这个方法不可能通过测试，效率也非常低。后来考虑了从后往前比较然后交换的方式，思路不清晰没有写成功。最后借鉴了官网第一种解题思路，即还是从后往前比较，找到第一个nums[i] 比nums[i+1]小的时候，再从nums[i+1]往后查找一个最小的比nums[i]大的元素，将该元素与nums[i]交换。交换后，再将从nums[i+1]到末尾的数值从小到大排序。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int total_num = nums.size();
        vector<int> temp;
        bool breakflag = true;
        int i = 0;
        int j = 0;

        while (i < total_num - 1 && breakflag)
        {
            if (nums[total_num - 1 - i] <= nums[total_num - 2 - i])
            {
                i++;
            }
            else
            {
                breakflag = false;//满足条件后就跳出循环
            }
        }
        if (i == 0)
        {
            temp.push_back(nums[total_num - 1]);
        }
        else if (i == total_num - 1)
        {
            sort(nums.begin(), nums.end());
            breakflag = true;//说明已经是最大组合，直接反向即可，不需要进行下面的查找处理
        }
        else
        {
            temp.assign(nums.end() - (i + 1), nums.end());
        }

        if (!breakflag)
        {
            //查找一个最小的比nums[total_num - 2 - i]大的元素,已经保证了查找集合由小到大排列，因而可以按序查找
            sort(temp.begin(), temp.end());
            while (temp[j] <= nums[total_num - 2 - i] && j < temp.size())
            {
                j++;
            }
            //swap(nums[total_num - 2 - i],temp[j]);//这句的内存消耗和运行时间都远不及下面这段
            int swap_temp = nums[total_num - 2 - i];
            nums[total_num - 2 - i] = temp[j];
            temp[j] = swap_temp;//将查找所得的两数交换
            sort(temp.begin(), temp.end());//将交换后的查找集合重新由小到大排序再赋值至原来数组的相应位置
            for (int m = 0; m < temp.size(); m++)
            {
                nums[total_num - 1 - i + m] = temp[m];
            }
        }

    }
};

执行用时：8 ms；内存消耗 8.8MB

Tips：平时可用自带模板函数完成上述过程

next_permutation(vector.begin(), vector.end());

第二次尝试：

思路：具体思路不变，重点在于简化函数并多用指针，之前针对“从nums[i+1]往后查找一个最小的比nums[i]大的元素，将该元素与nums[i]交换”这一处理比较复杂，其实只要从末尾往前查找第一个大于nums[i]的元素即可。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if (nums.size() < 2)
            return;
        vector<int>::iterator i;
        vector<int>::iterator j;
        vector<int>::iterator k;
        for (i = nums.end() - 1; i != nums.begin(); --i)
        {
            j = i - 1;
            if (*j < *i)
            {
                for (k = nums.end() - 1; k != j; --k)
                {
                    if (*k>*j)
                    {
                        swap(*k, *j);
                        sort(j + 1, nums.end());
                        return;
                    }
                }
            }
            if (j == nums.begin())
            {
                sort(nums.begin(), nums.end());
                return;
            }
        }
    }
};

执行用时：8 ms；内存消耗 8.4MB