60. Permutation Sequence

发表于 | 分类于

每日一题 2019 - 04 - 03

题目：

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:

  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.
  • Given k will be between 1 and n! inclusive.

Example 1:

1
2
Input: n = 3, k = 3
Output: "213"

Example 2:

1
2
Input: n = 4, k = 9
Output: "2314"

思路：

这个题让我们找到给定序列全拍列的第 K 个序列是什么；

常规思路就是写个全排列，找到第 K 个，可是这个题运用全排列算法会超时；

所以需要换个思路：

1）第k个排列的第一个元素在0-n中的位置为（k-1）/（n-1）！

2）在剩下的元素中继续找第一个；

3）依此类推；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {  //最高位等于k/(factorial(n-i))-1
public:
    string getPermutation(int n, int k) {
        vector<int> v(n);   //在v中选元素，最高位选定后，删除
        vector<int>::iterator it=v.begin();
        for(int i=0;i<n;i++)
            v[i]=i+1;
        string res;
        while(n)
        {
            it=v.begin();
            int index=(k-1)/factorial(n-1);
            res.push_back(v[index]+'0');
            k-=index*factorial(n-1);
            v.erase(it+index);
            n--;
        }
        return res;
    }
    int factorial(int n)  //求阶乘
    {
        int res=1;
        if(n<2)return res;
        while(n)
        {
            res*=n;
            n--;
        }
        return res;
    }
};
0%
undefined