Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

力扣60——第k个排列

death00 2020-01-14 20:57:41 阅读数:46 评论数:0 点赞数:0 收藏数:0

原题

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

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

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

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

说明:

  • 给定 n 的范围是 [1, 9]。
  • 给定 k 的范围是[1, n!]。

示例 1:

输入: n = 3, k = 3
输出: "213"

示例 2:

输入: n = 4, k = 9
输出: "2314"

解法

按照题目所描述的,其实就是按照排列规律,找出相应的数字。

每一位上可以存在的可能数字范围逐渐减少,因此我们需要记录一下当前用过哪些数字

每一位上前缀数字最终对应的可能性也是一个全排列,比如 n 为4时,当第1位定下来一个数字,其对应的所有数字组合有 3!,当第2位定下来后,其对应的数字组合就是2!。当你确认的数字越多,其组合也越少。

直接上代码:

class Solution {
// 当前数字是否用过,默认为false,代表没有用过
boolean[] used;
public String getPermutation(int n, int k) {
used = new boolean[n];
int all = 1;
for (int i = n - 1; i > 1; i--) {
all *= i;
}
StringBuilder sb = dfs(n, all, k);
return sb.toString();
}
/**
* n:当前还剩几个数字没有添加
* all:为了计算出当前数字属于第几组,例如n等于5时,all是4!,这样k/n就知道是第几组了
* k:所求结果是当前组的第几个
*/
public StringBuilder dfs(int n, int all, int k) {
// 组内偏移量
int offset = k % all;
// 当前是第几组
int groupIndex = k / all + (offset == 0 ? 0 : 1);
// 在当前没有被访问过的数字里,找第groupIndex个数字
int i = 0;
for (; i < used.length && groupIndex > 0; i++) {
if (!used[i]) {
groupIndex--;
}
}
// 用当前数字
StringBuilder result = new StringBuilder().append(i);
// 标记当前数字已经用过
used[i - 1] = true;
// 说明是最后一个数字
if (n == 1) {
return result;
}
// 确认一位数字后,其对应的可能性就在减少
return result.append(dfs(n - 1, all / (n - 1), (offset == 0 ? all : offset)));
}
}

提交OK,执行用时:2ms,内存消耗:34.4MB

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题应该主要就是找规律了,确认好边界情况就应该没什么问题。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

公众号:健程之道

版权声明
本文为[death00]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000021583778