60. 第k个排列（JS实现）

快来打我* 2023-02-17 08:54 41阅读 0赞

## 1 题目 ##

> 给出集合 \[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”

## 2 思路 ##

**这道题刚开始时直接深度优先遍历构造树，虽然通过了，但运行时间太长，后来发现有个技巧，每层for循环下面的子分支总数量为(m-1)！，其中m为当前没有用过的数的个数，比如第一层for循环，一个数也没用过，则每个分支对应的子分支的总数量为(n-1)！，这样就可以用k/(m-1)！来看一下需要的字符串在当前for循环的第几个分支下面，从而进行剪枝**

## 3代码 ##

/** * @param {number} n * @param {number} k * @return {string} */
    var getPermutation = function(n, k) { 
        if (n === 1) return "1";
    
        let nums = [];
        let x = 1;
        for (let i=1;i<=n;i++) { 
            nums.push('' + i);
            x *= i;
        }
        x = x / n;
    
        let ans = '';
        let index = 0;
        let y = Math.floor(k / x) !== k / x ? Math.floor(k / x) : k / x - 1;
    
        for (let i=0;i<n;i++) { 
            if (i < y) continue;    //这里对第一层for循环进行剪枝
            d(nums[i], k - y * x);
        }
    
        function d(str, k) { 
            if (ans) return;
    
            if (str.length === n && ++index === k) { 
                ans = str;
                return;
            }
    
            for (let i=0;i<n;i++) { 
                if (str.includes(nums[i])) continue;
                d(str + nums[i], k);
            }
        }
    
        return ans;
    };