Permutation Sequence

hard 原题链接：https://leetcode.com/problems/permutation-sequence/

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:

1. "123"

2. "132"

3. "213"

4. "231"

5. "312"

6. "321"

Given n and k, return the kth permutation sequence.

例子

Input: n = 3, k = 3

Output: "213"

Input: n = 4, k = 9

Output: "2314"

Note

• Given n will be between 1 and 9 inclusive.

• Given k will be between 1 and n! inclusive.

解法一

class Solution {
public:
    string getPermutation(int n, int k) {
        string s = "", res = "";
        vector<int>factorial(n + 1, 1);
        int sum = 1;
        for(int i = 1; i <= n; i++){
            s.push_back(i + '0');
            sum *= i;
            factorial[i] = sum;
        }
        k--;
        for(int i = 1; i <= n; i++){
            int index = k / factorial[n - i];
            res.push_back(s[index]);
            s.erase(s.begin() + index);
            k %= factorial[n - i];
        }
        return res;
    }
};

出处

The approach is mathematical. The idea is to keep selecting a digit and eliminating it from further selection based on value of K.

For example:

Given, N = 4, K = 9

There are 6 numbers starting with 1: 1234, 1243, 1324, 1342, 1423, 1432 There are 6 numbers starting with 2: 2134, 2143, 2314, 2341, 2413, 2431 Similarly, there are 6 numbers starting with 3 and 6 numbers starting with 4.

This is because when we have chosen one place out of 4 places (as N=4), there are 3 places remaining to be filled and those 3 places can be filled in 6 ways or (N-1)! ways.

So, we have to keep identifying which digit to choose.

Initially, we have to choose a digit from {1,2,3,4}.

Since K = 9, meaning it belongs to second set of six numbers and hence, would begin with 2.

Now, first place is chosen as 2 and output string becomes "2". This means we have eliminated 6 choices starting with 1 (1234, 1243, 1324, 1342, 1423, 1432).

Now, K would be updated as K = 9 - 6 = 3.

We now have to identify remaining 3 places with the digits {1,3,4} and with K = 3.

There are 2 numbers starting with 1: 134, 143 There are 2 numbers starting with 3: 314, 341 There are 2 numbers starting with 4: 413, 431

This is because when we have chosen one place out of 3 available places, there are 2 places remaining to be filled and those 2 places can be filled in 2 ways.

Since, K = 3, meaning it belongs to second set of two numbers and hence, answer would be appended with "3" and output string becomes "23". This means we have eliminated 2 choices starting with 1 (134, 143).

Now, K would be updated as K = 3 - 2 = 1.

We now have to identify remaining 2 places with the digits {1,4} with K = 1.

There is 1 number starting with 1: 14 There is 1 number starting with 4: 41

This is because when we have chosen one place out of 2 available places, there is only 1 place remaining to be filled and that 1 place can be only be filled in 1 ways.

Since, K = 1, meaning it belongs to first set of one number and hence, answer would be appended with "14" and output string becomes "2314".

Therefore, final answer becomes "2314".

解法二

class Solution {
public:
    string getPermutation(int n, int k) {
        string s = "";
        for(int i = 1; i <= n; i++) s.push_back(i + '0');
        while(--k) next_permutation(s.begin(), s.end());
        return s;
    }
};

next_permutation

解法三 backtracking

class Solution {
public:
    string getPermutation(int n, int k) {
        string s = "", res = "";
        for(int i = 1; i <= n; i++) s.push_back(i + '0');
        string path = s;
        int count = 0;
        DFS(s, 0, count, n, k, path, res);
        return res;
    }
    
    void DFS(string& s, int pos, int& count, int n, int k, string& path, string& res){
        if(count >= k || pos == n){
            if(++count == k) res = path;
            return;
        }
        for(int i = 0; i < n; i++){
            if(s[i] == '0') continue;
            path[pos] = s[i];
            s[i] = '0';
            DFS(s, pos + 1, count, n, k, path, res);
            s[i] = path[pos];
        }
    }
};