Next Permutation

    Find the next permutation in ascending order.

    Example

    For , the next permutation is [1,3,3,2]

    Note

    The list may contains duplicate integers.

    题解

    找下一个升序排列，C++ STL 源码剖析一书中有提及， 一小节中也有详细介绍，下面简要介绍一下字典序算法：

    1. 从后往前寻找索引满足 , 如果此条件不满足，则说明已遍历到最后一个。
    2. 从后往前遍历，找到第一个比a[k]大的数a[l], 即a[k] < a[l].
    3. 反转k + 1 ~ n之间的元素。

    Python

    Java

    和 Permutation 一小节类似，这里只需要注意在step 1中i == -1时需要反转之以获得最小的序列。对于有重复元素，只要在 step1和 step2中判断元素大小时不取等号即可。Lintcode 上给的注释要求（其实是 Leetcode 上的要求）和实际给出的输出不一样。

    复杂度分析

    最坏情况下，遍历两次原数组，反转一次数组，时间复杂度为 O(n), 使用了 temp 临时变量，空间复杂度可认为是 O(1).