LeetCode 题解：一顿操作猛如虎，一看击败百分五

偏执的太偏执、 2022-12-07 01:58 79阅读 0赞

大家好，我是吴师兄，今天分享一道和数学有关的算法题，题目不难，但不优化的话会出现 **一顿操作猛如虎，一看击败百分五** 的情况：）

### 题目描述 ###

给出集合 `[1,2,3,…,n]`，其所有元素共有 *n!* 种排列。

按大小顺序列出所有排列情况，并一一标记，当 *n = 3* 时, 所有排列如下：

"123"
    "132"
    "213"
    "231"
    "312"
    "321"

给定 *n* 和 *k*，返回第 *k* 个排列。

**说明：**

*  给定 *n* 的范围是 \[1, 9\]。
 *  给定 *k* 的范围是\[1, n!\]。

**示例 1:**

输入: n = 3, k = 3
    输出: "213"

**示例 2:**

输入: n = 4, k = 9
    输出: "2314"

来源：https://leetcode-cn.com/problems/permutation-sequence

### 题目解析 ###

一道比较偏数学的题目。

题意是给定 1 ～ n 的数字（n <= 9），因为数字所在的位置不同，这些数字可以组成的整数也不同。最后让你求按照组成的整数大小排序，排在第 k 的整数是多少。

要求全排列的话，时间和空间复杂度都是 `O(n!)`。

先看最直接的解法，通过暴力搜索，找出所有的全排列的情况，然后排序，直接就可以得出答案。

这么做的时间复杂度是 `O(n!log(n!))`。

很显然的是，这么做时间上面不符合要求，需要进一步优化算法。

首先考虑的一个问题是，**我们需不需要找出所有的组合情况？**

如果要找出所有的情况，那么时间上肯定是没法提高的。这其实就涉及到一个暴力搜索的剪支的问题，就拿 n = 3 为例，按照元素大小，全排列如下：

"123"
    "132"
    "213"
    "231"
    "312"
    "321"

这里，如果说 k = 5，那么是不是可以说以 “1” 和 “2” 开始的情况我们就不需要考虑了？

我们只需要从 “3” 开始的序列开始找就可以了，这样子可以很大程度上节省搜索的成本。

那么问题来了，**如何确定我们需要找的结果在不在以某个数字开头的区间内？**

其实，每个数字开头的序列总个数都是一样的，比如上面的以 “1”，“2”，“3” 开头的序列个数都是 2 个，我们只需要逐个排除就行了。

如果 k = 5，因为 5 > 2，说明结果不会在以 “1” 开头的区间中。又因为 5 > 4，说明结果不会在以 “2” 开头的区间中。

但是 5 < 6 的，所以我们需要在开头是 “3” 的序列中继续找。确定了开头数字是 3 之后，我们可以把 3 排除，然后继续去用同样的方法确定第二个数字，第三个数字。。。

这样做下来，时间上面是可以大大提高的。至于具体的时间复杂度是多少，这和具体的输入有关。但是空间方面，我们并不需要 `O(n!)` 的空间，n 的空间（函数栈空间）就足够了。

### 参考代码 ###

func getPermutation(n int, k int) string {
        nums := []int{}
    
        for i := 1; i <= n; i++ {
            nums = append(nums, i)
        }
    
        return helper(nums, k)
    }
    
    func helper(nums []int, k int) string {
        totalNums := 1
        // 计算以每个数字开头的序列个数
        for i := 1; i < len(nums); i++ {
            totalNums *= i
        }
    
        for i := range nums {
            // 以当前数字开头的话，前面的序列的总个数
            sum := (i + 1) * totalNums
    
            sub := k - sum
    
            // 说明结果是以当前数字开头
            // 去掉当前选中的数字，递归去确定接下来的数字
            if sub <= 0 {
                arr := []int{}
                arr = append(arr, nums[:i]...)
                arr = append(arr, nums[i+1:]...)
                return strconv.Itoa(nums[i]) + helper(arr, k - i * totalNums)
            }
        }
    
        return ""
    }