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

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

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

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:

Input: nums = [1]
Output: [1]

解法

返回当前序列在“字典序”中的下一个序列。

按照“字典序算法”生成下一个序列，字典序生成全排列的过程：

① 将N个元素从小到大递增排序，形成有序序列，这是字典中最小的排列 A A A；

② 在 A A A的有序部分，寻找最后一个满足 A [ i ] < A [ i + 1 ] A[i]<A[i+1] A[i]<A[i+1]的元素 A [ i ] A[i] A[i]；

③ 在 A [ i + 1 , N − 1 ] A[i+1,N-1] A[i+1,N−1]范围内找到大于 A [ i ] A[i] A[i]的最小数 A [ j ] A[j] A[j]，交换 A [ i ] A[i] A[i]与 A [ j ] A[j] A[j]；

④ 对 A [ i + 1 , N − 1 ] A[i+1,N-1] A[i+1,N−1]范围内的元素进行翻转，得到字典序中的下一个序列；

⑤ 重复步骤②~④，直到所有元素按照从大到小逆序排列，全排列完成。

字典序生成全排列类似于动态规划，根据已知的第一个序列，生成下一个序列。

代码实现

public static void nextPermutation(int[] nums) {
    int len = nums.length;
    int i = len - 2;
    // 从前向后找到最后一组正序，等价于从后向前找第一组逆序
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    // 翻转倒序数组
    if (i < 0) {
        reverse(nums, 0, len - 1);
        return;
    }
    // 从后向前找到大于 nums[i] 的最小的数
    int j = len - 1;
    while (j > i + 1 && nums[j] <= nums[i]) {
        j--;
    }
    swap(nums, i, j);
    reverse(nums, i + 1, len - 1);
}

/**
     * 翻转数组
     *
     * @param arr   数组
     * @param begin 开始下标
     * @param end   结束下标
     */
private static void reverse(int[] arr, int begin, int end) {
    while (begin < end) {
        swap(arr, begin, end);
        begin++;
        end--;
    }
}

/**
     * 交换数组中的两个元素
     *
     * @param nums 数组
     * @param idx1 下标1
     * @param idx2 下标2
     */
private static void swap(int[] nums, int idx1, int idx2) {
    int tmp = nums[idx1];
    nums[idx1] = nums[idx2];
    nums[idx2] = tmp;
}

时间复杂度： O ( N ) O(N) O(N)

总结

直接使用“字典序算法”生成下一个序列。