【leetcode】60 Permutation Sequence

发表于 | 分类于 ，


描述

全排列，按顺序标好号，输入一个 k 返回标号为 k 的全排列。

样例

样例1

1
2
输入: 3 5
输出: [3 2 1]

样例2

1
2
输入: 3 2
输出: [1 3 2]

思路

写出所有全排列，保存在数组中，之后返回值。这样空间会很大，不符合要求，优化后直接保存一个结果，可以通过测试。

note: 通过交换两个值的全排列算法产生的不是顺序全排列，而 temp 的增加弹出可以符合要求

上述方法勉强能通过测试，还有更好的方法，思路是直接锁定这个值是多少。

观察 [1,2,3] 的全排列，我们可以把它分成下述问题
1 [2,3]
2 [1,3]
3 [1,2]

显然每一个数作为开始都有 (n-1)! 个可能，依据这样的思路，我们可以精确找到这个值，复杂度仅为 O(n)

代码

回溯

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 {
    int count ;
public:
    string getPermutation(int n, int k) {
        string res="";
        count = 0;
        string s ="";
        for(int i=1;i<=n;i++){
            s += i+'0';
        }
        string temp ="";
        backtarck(res,s,temp, k);
        return res;
    }

    void backtarck(string & res,const string  &s, string temp,const int & k){
        if(res != ""){return ;}
        if(temp.size() == s.size()){
            count++;
            if(count == k){ res = temp; } 
            return ;
        }
        for(int i= 0;i<s.size();i++){
            if(temp.find(s[i]) == temp.npos){
                 temp.push_back(s[i]);
                 backtarck(res,s,temp,k);
                 temp.pop_back();
            }
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> factorial(n,1);
        string num = "123456789";
        string res;
        for(int i = 1; i< n; ++i) factorial[i] = factorial[i-1]*i;
        --k;
        for(int i = n; i>=1; --i){
            int j = k/factorial[i-1];
            res.push_back(num[j]); //string也可以用push_back
            k = k % factorial[i-1];
            num.erase(j,1); //很重要，用过一次后面的permutation就不能再出现了  
        }
        return res;
    }
};

参考

原题链接