LeetCode算法题:第k个排列getPermutation
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode算法题:第k个排列getPermutation,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1543字,纯文字阅读大概需要3分钟。
内容图文
![LeetCode算法题:第k个排列getPermutation](/upload/InfoBanner/zyjiaocheng/716/8e8d658adc2b4cc8b585ba5c9284de71.jpg)
给出集合 [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 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。