【LeetCode 60】第k个排列-蒲公英云

【LeetCode 60】第k个排列

清疚 2022-12-04 05:29 242阅读 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"

解题思路

对于这道题目，我们可以找一些规律，然后再求解。

我们知道，ｎ个数字的排列一共有 n! 个，以１开头的排列有 (n-1)! 个，以２、３…… n 为开头的也是(n-1)! 个。

以n = 4, k = 9为例，1234的排序如下：

在这里插入图片描述
我们要选的是第九个数字，每一组是六个数字，可以直接9 % 6 = 3 ，然后在第二组寻找第三个数组就可以了，也就是2314。

我们可以将它们看成不同的组。第 k 个排列落在哪个组，直接到那个组去找，大大缩小了寻找的范围。

这上面就是题目的大致思路了，下面就来看下具体解法。

我们可以先将1- 4 放在数组中：[1,2,3,4]，索引 0 对应数字 1，有一个错位，所以我把 k 减 1 处理。

（9-1）/ 3! 取整等于索引1，对应数组中的2，就确定了第一个数为2。

现在就剩下三个数字，那就是在三个数字的全排列中按照上述方法继续寻找。

该方法的时间复杂度为O(n2)

代码实现

/** * @param {number} n * @param {number} k * @return {string} */
var getPermutation = function(n, k) { 
    const nums = []
    let factorial = 1   // 阶乘的结果
    for(let i = 1; i <= n; i++){ 
        nums.push(i)
        factorial = factorial * i
    }
    k --
    let resStr = ''
    while(nums.length > 0){ 
        factorial = factorial / nums.length
        const index = k / factorial | 0
        resStr += nums[index]
        nums.splice(index, 1)
        k = k % factorial
    }
    return resStr
};