daily leetcode - permutation-sequence - !
题目地址
https://leetcode.com/problems/permutation-sequence/
题目描述
The set [1,2,3,..., _n_ ]
contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k , return the k th permutation sequence.
Note:
- Given n will be between 1 and 9 inclusive.
- Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
思路
这道题是让求出n个数字的第k个排列组合,由于其特殊性,我们不用将所有的排列组合的情况都求出来,然后返回其第k个,我们可以只求出第k个排列组合即可,那么难点就在于如何知道数字的排列顺序,可参见网友喜刷刷的博客,首先我们要知道当n = 3时,其排列组合共有3! = 6种,当n = 4时,其排列组合共有4! = 24种,我们就以n = 4, k = 17的情况来分析,所有排列组合情况如下:
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412 <--- k = 17
3421
4123
4132
4213
4231
4312
4321
我们可以发现,每一位上1,2,3,4分别都出现了6次,当最高位上的数字确定了,第二高位每个数字都出现了2次,当第二高位也确定了,第三高位上的数字都只出现了1次,当第三高位确定了,那么第四高位上的数字也只能出现一次,下面我们来看k = 17这种情况的每位数字如何确定,由于k = 17是转化为数组下标为16:
最高位可取1,2,3,4中的一个,每个数字出现3!= 6次(因为当最高位确定了,后面三位可以任意排列,所以是3!,那么最高位的数字就会重复3!次),所以k = 16的第一位数字的下标为16 / 6 = 2,在 "1234" 中即3被取出。这里我们的k是要求的坐标为k的全排列序列,我们定义 k' 为当最高位确定后,要求的全排序列在新范围中的位置,同理,k'' 为当第二高为确定后,所要求的全排列序列在新范围中的位置,以此类推,下面来具体看看:
第二位此时从1,2,4中取一个,k = 16,则此时的 k' = 16 % (3!) = 4,注意思考这里为何要取余,如果对这24个数以6个一组来分,那么k=16这个位置就是在第三组(k/6 = 2)中的第五个(k%6 = 4)数字。如下所示,而剩下的每个数字出现2!= 2次,所以第二数字的下标为4 / 2 = 2,在 "124" 中即4被取出。
3124
3142
3214
3241
3412 <--- k' = 4
3421
第三位此时从1,2中去一个,k' = 4,则此时的k'' = 4 % (2!) = 0,如下所示,而剩下的每个数字出现1!= 1次,所以第三个数字的下标为 0 / 1 = 0,在 "12" 中即1被取出。
3412 <--- k'' = 0
3421
第四位是从2中取一个,k'' = 0,则此时的k''' = 0 % (1!) = 0,如下所示,而剩下的每个数字出现0!= 1次,所以第四个数字的下标为0 / 1= 0,在 "2" 中即2被取出。
3412 <--- k''' = 0
那么我们就可以找出规律了
a1 = k / (n - 1)!
k1 = k
a2 = k1 / (n - 2)!
k2 = k1 % (n - 2)!
...
an-1 = kn-2 / 1!
kn-1 = kn-2 % 1!
an = kn-1 / 0!
kn = kn-1 % 0!
代码如下:
class Solution {
public:
string getPermutation(int n, int k) {
string res;
string num = "123456789";
vector<int> f(n, 1);
for (int i = 1; i < n; ++i) f[i] = f[i - 1] * i;
--k;
for (int i = n; i >= 1; --i) {
int j = k / f[i - 1];
k %= f[i - 1];
res.push_back(num[j]);
num.erase(j, 1);
}
return res;
}
};
思路2
LeetCode 上关于排列的题目截止目前(2020-01-06)主要有三种类型:
- 生成全排列
- 生成下一个排列
- 生成第 k 个排列(我们的题目就是这种)
我们不可能求出所有的排列,然后找到第 k 个之后返回。因为排列的组合是 N!,要比 2^n 还要高很多,非常有可能超时。我们必须使用一些巧妙的方法。
我们以题目中的 n= 3 k = 3 为例:
- "123"
- "132"
- "213"
- "231"
- "312"
- "321"
可以看出 1xx,2xx 和 3xx 都有两个,如果你知道阶乘的话,实际上是 2!个。 我们想要找的是第 3 个。那么我们可以直接跳到 2 开头,我们排除了以 1 开头的排列,问题缩小了,我们将 2 加入到结果集,我们不断重复上述的逻辑,知道结果集的元素为 n 即可。
关键点解析
- 找规律
- 排列组合
代码
- 语言支持: Python3
import math
class Solution:
def getPermutation(self, n: int, k: int) -> str:
res = ""
candidates = [str(i) for i in range(1, n + 1)]
while n != 0:
facto = math.factorial(n - 1)
# i 表示前面被我们排除的组数,也就是k所在的组的下标
# k // facto 是不行的, 比如在 k % facto == 0的情况下就会有问题
i = math.ceil(k / facto) - 1
# 我们把candidates[i]加入到结果集,然后将其弹出candidates(不能重复使用元素)
res += candidates[i]
candidates.pop(i)
# k 缩小了 facto * i
k -= facto * i
# 每次迭代我们实际上就处理了一个元素,n 减去 1,当n == 0 说明全部处理完成,我们退出循环
n -= 1
return res
本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode