LeetCode31-下一个排列

解题记录
397 words , 1 mins.

题目描述

给定一个整数序列，给出整数序列升序排序的下一个序列。如果不存在更大的序列，则返回最小的一个序列。

示例：

输入：nums = [1, 2, 3]
输出：[1, 3, 2]

输入：nums = [3, 2, 1]
输出：[1, 2, 3]

输入：nums = [1, 1, 5]
输出：[1, 5, 1]

题目解析

我的思路是从后往前依次查看 nums[i] 和 nums[i + 1] 的大小关系，如果 nums[i] > nums[i + 1]，则说明倒数第 1 至倒数第 i 个元素，都是降序排序，不可能存在更大的序列。如果 nums[i] < nums[i + 1]，则说明仅调换两个元素的位置，就能得到一个更大的序列，但是这个序列不一定是“下一个”序列：比如 [2 3 5 1]，调换 3 和 5 的位置，得到 [2 5 3 1]，是一个更大的序列，但比之小的 [2 3 1 5] 才是真正的下一个序列。其实将倒数第 i 位及之后的部分单独拿出来看： [3 5 1]，此时 3 是第一个元素，而后面的元素都是降序排序，说明 3 开头的排序已经结束了，下一个更大的序列应该是比 3 大，比其他元素小的元素 x 开头的排序，只要将这个元素 x 的位置找到，和 3 替换一下位置，再对起始元素之后的元素进行升序排序，就能得到下一个序列，即以 x 开头的最小的序列。

代码实现

Kotlin 代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * @time        2026-05-29 11:43
 * @author      qiukui-note
 * @description LeetCode Q.31 求整数序列的下一个排列
 */

class Solution31 {
    fun nextPermutation(nums: IntArray) {
        val n = nums.size
        for (i in n - 2 downTo 0) {
            if (nums[i] < nums[i + 1]) {
                val minBiggerIndex = findMinBigger(nums, nums[i], i + 1)
                swap(nums, i, minBiggerIndex)
                resort(nums, i + 1)
                return
            }
        }

        resort(nums, 0)
    }

    fun resort(nums: IntArray, index: Int) {
        val n = nums.size - index
        for (i in 0..<n) {
            val k = n - 1 - i
            for (j in 0..<n - 1 - i) {
                if (nums[j + index] > nums[j + index + 1]) {
                    swap(nums, j + index, j + index + 1)
                }
            }
        }
    }

    fun swap(nums: IntArray, index1: Int, index2: Int) {
        val temp = nums[index2]
        nums[index2] = nums[index1]
        nums[index1] = temp
    }

    fun findMinBigger(nums: IntArray, target: Int, endIndexFromTail: Int): Int {
        var nextValueIndex = -1
        var nextValue = Int.MAX_VALUE
        for (i in (nums.size - 1) downTo endIndexFromTail) {
            if (nums[i] in (target + 1)..<nextValue) {
                nextValue = nums[i]
                nextValueIndex = i
            }
        }
        return nextValueIndex
    }
}

fun main() {
    val arrs = arrayOf(
        intArrayOf(1, 2, 3),
        intArrayOf(1, 3, 2),
        intArrayOf(2, 1, 3),
        intArrayOf(2, 3, 1),
        intArrayOf(3, 1, 2),
        intArrayOf(3, 2, 1),
        intArrayOf(1),
        intArrayOf(1, 2),
        intArrayOf(2, 1),
        intArrayOf(5, 4, 7, 5, 3, 2),
        intArrayOf(1, 5, 1),
        intArrayOf(5, 1, 1)
    )
    val solution = Solution31()
    for (nums in arrs) {
        println("=====")
        println(nums.contentToString())
        solution.nextPermutation(nums)
        println(nums.contentToString())
    }
}