下一个排列 next_permutation

获取排列的下一个

可以直接用api，也可以自己写

api

next_permutation(nums.begin(),nums.end()); // STL功能和题目描述一致

题目：

原地址：https://leetcode-cn.com/problems/next-permutation/

整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。 给你一个整数数组 nums ，找出 nums 的下一个排列。

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

示例 1：

输入：nums = [1,2,3] 输出：[1,3,2] 示例 2：

输入：nums = [3,2,1] 输出：[1,2,3] 示例 3：

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

提示：

1 <= nums.length <= 100 0 <= nums[i] <= 100

思路：

可知，下一个排序就是比当前排序稍微大一点点的一个排序，那么为了只大一点点，我们需要尽可能的将低位的一个较小的数换成其后边的一个大一点的数。换过之后，这个数后边的按照升序排列，达到最小的数，这样就实现了只增加一点点。

那么需要找尽可能靠后的一个数，并且这个数之后，有比他大的一个数，可以让他交换。

这样的数有一个特点，就是从数组的最后开始两个两个的比较，一旦出现前面的数比后边的数小，那么这个数，就是我们要找的数。

那么我们再从数组最后向前找一个只比这个数大一点点的一个数，就是我们要用来替换的数。

替换后你会发现，从数组的尾部往前看，他还是一个升序，我们需要把这个升序改为降序，只需要双指针，头尾交换即可。

代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<map>
using namespace std;

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2, j = nums.size() - 1;
        while (i >= 0 && nums[i] >= nums[j])
        {
            i--; j--;
        }
        if (i >= 0)
        {
            int index = nums.size() - 1;
            while (nums[i] >= nums[index])index--;
            swap(nums[i], nums[index]);
        }
        for (int k = 0; k < (nums.size() - j) / 2; k++)swap(nums[k + j], nums[nums.size() - k - 1]);
    }
};

int main()
{
    int nums[] = { 1,5,1 };
    vector<int> v_nums;
    for (int i = 0; i !=3; i++)v_nums.push_back(nums[i]);
    Solution s;
    s.nextPermutation(v_nums);
    for (int i = 0; i != v_nums.size(); i++)
    {
        cout << v_nums[i] << " ";
    }
    cout << endl;
    return 0;
}