31-下一个排列

题目

0031. 下一个排列

给你一个整数数组 nums ，请你找出数组中字典序最小的下一个排列。数组的字典序是由数组中的元素构成的数字的大小决定的。例如，[1,2,4] 的字典序比 [1,2,3] 小。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

你必须原地修改，只允许使用额外常数空间。

算法解析：

"下一个排列"（Next Permutation）这道算法题的目标是重新排列数字，以得到给定数字序列的下一个更大的排列。如果不存在这样的排列，则将数字重新排列成最小的顺序（即升序排列）。在 Go 语言中实现这个算法，可以遵循以下步骤：

从右向左找第一个递减元素：遍历数组，从后向前查找第一个满足 nums[i-1] < nums[i] 的位置 i。这意味着 nums[i-1] 可以与一个更大的数交换来得到更大的排列。
找到可以交换的更大数：如果找到了这样的 i，则从数组最后开始，找到第一个大于 nums[i-1] 的数 nums[j]。
交换这两个数：交换 nums[i-1] 和 nums[j]。
翻转 i 后面的所有数：最后，为了得到刚好比之前排列大的下一个排列，需要将位置 i 之后的所有数翻转成升序。

下面是这个算法的 Go 语言实现：

package main

import (
    "fmt"
)

func nextPermutation(nums []int) {
    n := len(nums)
    if n <= 1 {
        return
    }

    // Step 1: Find the first decreasing element
    i := n - 1
    for i > 0 && nums[i-1] >= nums[i] {
        i--
    }

    if i > 0 {
        // Step 2: Find the number just larger than nums[i-1]
        j := n - 1
        for nums[j] <= nums[i-1] {
            j--
        }
        // Step 3: Swap them
        nums[i-1], nums[j] = nums[j], nums[i-1]
    }

    // Step 4: Reverse the elements after the i-th position
    reverse(nums[i:])
}

func reverse(nums []int) {
    for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
        nums[i], nums[j] = nums[j], nums[i]
    }
}

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

这段代码首先定义了 nextPermutation 函数来实现算法的主要逻辑，然后用 reverse 函数来翻转数组的一部分。在 main 函数中，你可以用任何你想测试的数字序列来调用 nextPermutation 函数，并观察结果。

其中"从右向左找第一个递减元素" 这个步骤是指在给定的数字序列中从右边开始向左边查找，直到找到第一个比它右边数字小的数字。这个步骤是为了找到可以进行交换以得到下一个更大排列的起点。这里的“递减”是指数字序列在这一点开始从右向左是降序的。

输入的数组不需要是有序的。这个算法的目的就是在给定任意顺序的数字序列中找到按字典顺序下一个更大的排列。如果整个数组都是降序的（即最大的排列），那么它的“下一个排列”就是最小的排列，即这些数字的升序排列。

让我们用一个具体的例子来解释这个过程：

假设输入数组为 [1, 3, 5, 4, 2]。

从右向左找第一个递减元素：从右边开始，2 < 4，4 < 5，不满足条件；但是 5 > 3，所以第一个递减元素是 3。
找到可以交换的更大数：在 3 的右边找到比 3 大的最小数，这里是 4。
交换这两个数：交换 3 和 4，数组变成 [1, 4, 5, 3, 2]。
翻转 i 后面的所有数：翻转 4 后面的所有数，得到 [1, 4, 2, 3, 5]。

这样得到的 [1, 4, 2, 3, 5] 就是原始数组 [1, 3, 5, 4, 2] 的下一个排列。

题目​

题目