【LeetCode练习题】Permutation Sequence

时间:2022-02-26 08:46:29

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):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "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;
}
};