【LeetCode】 60. Permutation Sequence

Description

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.

一個集合[1,2,3,…,n]，它總共擁有n!種不同的排列組合。
以下照順序列出了n=3的時候的所有組合：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

給予n和k，請回傳第k種排列。

提示：

• n將會介於1到9之間(包含)。
• k將會介於1到n!之間(包含)。

Example:

Example 1:

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


Example 2:

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

Solution

• 因為我這類的題目很弱，直接使用了algorithm函式庫裡面的next_permutation。
• 缺點是速度很慢，因為理論上可以直接一步求得結果，但用這個方法你必須用Loop去跑k種組合。

Code

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

tags: LeetCode C++