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 (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
题目意思:
又是全排列。
【LeetCode练习题】Next Permutation
【LeetCode练习题】Permutations
本题的意思是在一个全排列中,找第k个全排列。如第一个是123,第二个是132……
n在[1,9]之间。
解题思路:
开始的时候,看到这个全排列我就想到之前做的两个排列题了,一个是求出所有的排列,一个是求出给定排列的下一个排列。
于是我尝试先求出所有的排列,再根据k返回指定位置的排列。结果果然 time limit exceed!
我又尝试了一个for循环从第一个排列开始,不断的求出下一个排列直到第k个。结果果然 memory limit exceed !
于是我直到投机取巧是行不通的了,这一题一定有属于他自己的解法在里面。
这题的解法是这样子的:
- 以 1 2 3 4 举例,n=4,k = 10. 试着在纸上画出分别以 1 2 3 4 为根节点的四棵树先。
- 第一层,以1 2 3 4 为根节点的每一棵树都有6个叶节点,6 = 3!,在第一棵树里第二层中,以2 3 4 为根节点的三个子树分别有 2 个叶节点, 2 = 2!,以2为子节点的子树中,有1!个叶节点。再往下有0!个叶节点。
- 开始的时候有一个vector num,依次存着 1-n,每向ret字符串里添加一个,就erase掉那个数。(发现vector的erase真是方便啊 !)
- 注意循环之前要进行 k--。因为我们的vector下标是从0开始的,所以假如 k 等于6的话,我们的结果应该是在以1为根节点的第一个树里,用 k / 3!反而等于 1 落在了以2为根节点的树里头了。
- 全程,注意count 和 k 的变化就行了,k / count 表示在当前层落在哪一棵数中, k % count 表示下一层的第几个叶节点。
代码如下:
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> num;
int count = ;
for(int i = ; i <= n; i++){
num.push_back(i);
count *= i;
}
//count == n!
string ret = "";
k--;
for(int i = ; i < n; i++){
count = count / (n-i);
int selected = k / count;
ret += ('' + num[selected] );
num.erase(num.begin()+selected);
k = k % count;
}
return ret;
}
};