描述

实现获取下一个排列的函数，算法需要将给定的数字序列重新排序成字典序列中的下一个更大的排列；

如果不存在下一个更大的排列，则将数字排成最小的数字；

必须在原地进行排序，只能够使用常数级别的额外空间。

示例：

1，2，3 -> 1，3，2；

3，2，1 -> 1，2，3

分析

这道题的关键是要理解算法原理：

1，从右向左遍历数组，找到第一个打破数组升序性质的数组的id:violateIdx；

2，从右向左遍历数组，找到第一个大于S[violateIdx]值的数字的索引firstBiggerThanViolateIdx;

3，交换S[violateIdx]和S[firstBiggerThanViolateIdx]；

4，将violateIdx之后的元素进行逆转；

了解算法原理后，代码的实现很容易：

void nextPermutation(int A[], int n)
{
    //从右向左找到第一个违反升序序列的index
    int violateIdx = -1;
    for(int i=n-1; i>0; --i) {
        if (A[i] > A[i-1]) {
            violateIdx = i - 1;
            break;
        }
    }
    
    if (violateIdx != -1) {
        // 从右向左查找第一个大于violateIdx值的索引
        int firstBiggerThanViolateIdx = n-1;
        for(int i=n-1; i>=0; --i) {
            if (A[i] > A[violateIdx]) {
                firstBiggerThanViolateIdx = i;
                break;
            }
        }
        
        //交换violateIdx 和 firstBiggerThanviolateIdx
        int temp = A[violateIdx];
        A[violateIdx] = A[firstBiggerThanViolateIdx];
        A[firstBiggerThanViolateIdx] = temp;
    }
    
    // 逆序元素
    int i = violateIdx + 1;
    int j = n - 1;
    while (i < j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
        ++i;
        --j;
    }
}

算法的时间复杂度为O(n)，空间复杂度为O(1)。

---

代码在这儿