60、第k个排列

leetcode

Created At : 2020-07-26 00:19

Count:433 Views 👀 :

Comment:

说明：
示例 1:
示例 2:
深度优先遍历+剪枝

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

深度优先遍历+剪枝

public int[] factorials = {1,1,2,6,24,120,720,5040,40320,362880};
    // 主函数
    public String getPermutation(int n, int k) {
        int[] nums = new int[n];
        boolean[] used = new boolean[n];
        for (int i = 0;i < n;i++) {
            nums[i] = i+1;
            used[i] = false;
        }
        
        List<String> pre = new ArrayList<>();
        return dfs(nums,used,n,k,0,pre);
    }
    
    // 深度优先遍历 剪枝
    private String dfs(int[] nums,boolean[] used,int n, int k,int depth,List<String> pre) {
        if (depth == n) { // 完成一个排列
            StringBuilder sb = new StringBuilder();
            for (String c : pre) {
                sb.append(c);
            }
            
            return sb.toString();
        }
        // 逐个开始求解，保证排列顺序从小到大
        for (int i = 0;i < n;i++) {
            if (used[i]) {// 已经使用过了
                continue;
            }
            
            // 剪枝
            /*  说明：
                因为从1开始遍历，深度从0开始， 
                如果当前的深度，将(n - depth)!个情况分为(n - depth)个(n - depth - 1)!情况，直到直到目标值。

                逐渐缩小区间，逐渐确定每一位的值
            */
            if (factorials[n - 1 - depth] < k) { // 排列数小于k个，则剪枝。因为本次排列集合不可能含有第k个排列。
                k -= factorials[n - 1- depth];// 减去排列数量，开始下一轮的遍历
                continue;
            }
            
            pre.add(nums[i] + "");
            used[i] = true;
            return dfs(nums,used,n,k,depth + 1,pre);
        }
        
        throw new RuntimeException("参数错误");
    }

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com