LeetCode算法题：第k个排列getPermutation

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode算法题：第k个排列getPermutation，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1543字，纯文字阅读大概需要3分钟。

内容图文

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：回溯法，找到第k行的排列。

	int step = 0;
    String result="";
    public String getPermutation(int n, int k) {
        boolean[] adj = new boolean[n];
        StringBuilder sb=new StringBuilder();
        dfs(n, k, adj, sb);
        return result;
    }


    public void dfs(int n, int k, boolean[] adj,StringBuilder string) {

        for (int i = 0; i < n; i++) {
        	//退出条件，当找到k行时将结果输出至result中。
            if (string.length() == n) {
                step++;
                if (step == k)result = string.toString();
                return;
            }
            if (adj[i] == true) continue;
            //找到k行后不必判断
            if (step < k) {
                string.append(i + 1);
                adj[i] = true;
                dfs(n, k, adj, string);
                adj[i] = false;//回溯
                string.deleteCharAt(string.length()-1);
            }
        }
        return;
    }

思路2：利用数学方法推出排列行（未掌握）

public String getPermutation(int n, int k) {
        StringBuilder stringBuilder = new StringBuilder();
        k--;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i + 1);
        }
        while (!list.isEmpty()) {
            int fun = func(n-- - 1);
            stringBuilder.append(list.get(k / fun));
            list.remove(k / fun);
            k %= fun;
        }
        return stringBuilder.toString();

    }

    public int func(int n) {
        if (n == 1 || n == 0)
            return 1;
        return func(n - 1) * n;
    }

内容总结

以上是互联网集市为您收集整理的LeetCode算法题：第k个排列getPermutation全部内容，希望文章能够帮你解决LeetCode算法题：第k个排列getPermutation所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---