LeetCode第60题找出集合 1,2,3…n 组成的排列中第 k 小的排列-一一网

题目

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

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

“123”
“132”
“213”
“231”
“312”
“321”

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

LeetCode传送门 60.排列序列

解法

一开始我准备用最笨的办法解题，首先把所有的排列组从小到大算出来，然后取出第k个。结果超时了，后来使用了数学方法搞定了，先来看看我的暴力法吧?。

暴力法

var getPermutation = function (n, k) {
    // 新建一个数组 permutationList 记录已经被使用过的元素
    const originList = [], permutationList = []
    let i = 0
    while (i < n) {
        originList.push(++i)
    }
    for (let i = 0; i < n; i++) {
        const newAns = [originList[i]]
        getsubPermutation(newAns, originList, permutationList, n)
    }
    return permutationList[k - 1]
};
// 挨个组合子排列
function getsubPermutation(newAns, nums, ans, length) {
    if (newAns.length === length) {
        ans.push(newAns.join(''))
        return
    }
    for (let i = 0; i < length; i++) {
        // 遍历所有元素如果当前元素被使用了就跳过
        if (newAns.includes(nums[i])) {
            continue
        }
        const _newAns = [...newAns, nums[i]]
        getsubPermutation(_newAns, nums, ans, length)
    }
}
复制代码

显然这样是不行的，他在 n = 9 的时候就会超时，虽然也能算出答案，所以还需要用正确的方法才行，那就是数学法。

数学法

对于 n 个不同的元素（例如数 1, 2,⋯,n），它们可以组成的排列总数目为 n!。

所以我们可以根据 k 的大小来确定 a1 。

原理是这样的

以 1 为 a1的排列一共有 (n−1)! 个；

以 2 为 a1的排列一共有 (n-1)! 个；

以 3 为 a1的排列一共有 (n-1)! 个；

……

以 n 为 a1的排列一共有 (n−1)! 个。

如果 k <= (n−1)! 就可以确定排列的首个元素为 1

如果 (n−1)! < k <= 2(n−1)! 就可以确定排列的首个元素为 2

如果 (n-1)(n−1)! < k <= n(n−1)! 就可以确定排列的首个元素为 n

所以第 k 个排列的首个元素就是：Math.fool(k-1/(n-1)!) + 1

这样一来，我们就把原问题转化成了一个完全相同但规模减少 1的子问题：

求集合 [1,2,…,n] 排除已使用元素 a1 这 n−1 个元素组成的排列中，第 k’ 小的排列。

然后问题被不断的缩小成单个元素组成的排列到这一步就已经求出解了

var getPermutation = function (n, k) {
    // 初始化结果、被使用元素的集合、集合元素容器、下一个子排列的元素数量 n
    let permutation = '', permutationElementSet = new Set(), allElement = [], nextN = n
    const i = k - 1
    
    // 初始化所有元素
    for (let j = 1; j <= n; j++) {
        allElement.push(j)
    }
    
    // 计算a1
    const a1 = Math.floor(i / getFactorial(n - 1)) + 1
    permutation += a1

    permutationElementSet.add(a1)
    //排除已经被使用过的元素
    allElement = allElement.filter(element => {
        return !permutationElementSet.has(element)
    })
    // 直到所有的子排列被计算完才结束
    while (permutation.length !== n) {
        // 不断计算子排列的首项a1
        permutation += getA1(nextN, i, allElement, permutationElementSet)
        // 排除已经被使用过的元素
        allElement = allElement.filter(element => {
            return !permutationElementSet.has(element)
        })
        nextN--
    }

    return permutation

};
// 计算子排列的首项a1
function getA1(n, i, allElement, set) {
    // 计算首项所在排列的索引 k' 
    const a1Index = Math.floor(i % getFactorial(n - 1))
    // 获得首项 a1 （ (n-1)个元素集合组成的排列每一个首项元素含有 (n-2)!个子组合  ）
    const a1 = allElement[Math.floor(a1Index / getFactorial(n - 2))]
    set.add(a1)
    return a1
}

// 求阶乘
function getFactorial(n) {
    let res = 1
    while (n > 1) {
        res *= n
        n--
    }
    return res
}
复制代码