一、 问题描述

Leecode第三十一题，题目为：

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

问题理解为：

实现next置换，它将数字重新排列到字典上的next更大的数字置换中。
如果这样的安排是不可能的，它必须重新安排它作为最低的可能的顺序(即，按升序排序)。
替换必须到位，并且只使用固定的额外内存。
这里有一些例子。输入在左边一列，相应的输出在右边一列。
1、2、3→1 3 2
3、2、1→1、2、3
1、1、5→1 5 1

说明:

二、算法思路
1、
2、

三、实现代码

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int i, j, n = num.size();
        for (i = n - 2; i >= 0; --i) {
            if (num[i + 1] > num[i]) {
                for (j = n - 1; j > i; --j) {
                    if (num[j] > num[i]) break;
                }
                swap(num[i], num[j]);
                reverse(num.begin() + i + 1, num.end());
                return;
            }
        }
        reverse(num.begin(), num.end());
    }
};

转：https://www.cnblogs.com/grandyang/p/4428207.html