[数据结构与算法]2022-01-07：下一个排列。实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。 如果不存在下一个更大的排列，则将数字重新排列成

2022-01-07：下一个排列。实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
来自力扣31。

答案2022-01-07：

从右往左遍历，遇到降序停止。交换，反序。
时间复杂度：O(N)。
空间复杂度：O(1)。

代码用golang编写。代码如下：

package main

import (
    "fmt"
)

func main() {
    nums := []int{1, 3, 2}
    nextPermutation(nums)
    fmt.Println(nums)
}

func nextPermutation(nums []int) {
    N := len(nums)
    // 从右往左第一次降序的位置
    firstLess := -1
    for i := N - 2; i >= 0; i-- {
        if nums[i] < nums[i+1] {
            firstLess = i
            break
        }
    }
    if firstLess < 0 {
        reverse(nums, 0, N-1)
    } else {
        rightClosestMore := -1
        // 找最靠右的、同时比nums[firstLess]大的数，位置在哪
        // 这里其实也可以用二分优化，但是这种优化无关紧要了
        for i := N - 1; i > firstLess; i-- {
            if nums[i] > nums[firstLess] {
                rightClosestMore = i
                break
            }
        }
        //swap(nums, firstLess, rightClosestMore);
        nums[firstLess], nums[rightClosestMore] = nums[rightClosestMore], nums[firstLess]
        reverse(nums, firstLess+1, N-1)
    }
}

func reverse(nums []int, L, R int) {
    for L < R {
        nums[L], nums[R] = nums[R], nums[L]
        L++
        R--
    }
}

执行结果如下：

左神java代码