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:

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Example:

Example 1:

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

Example 2:

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

Link:

https://leetcode.com/problems/permutation-sequence/description/

解题方法：

找第k个permutation, 当给定n和k时：
以1开头的permutation有(n - 1)!个，如果k > (n - 1)! 说明一定不是以1开头的，同理2其他数开头的permutation都有(n - 1)!个，所以可以一次类推一位一位得到所要的permutation。

Tips:

本来想用linked list来优化时间复杂度，做完才发现linked list也是O(N^2)的。。。。

Time Complexity：

O(N^2)

完整代码：

public:
    int val;
    node(int i) {val = i; next = NULL;}
    node* next;
};
string getPermutation(int n, int k) {
    int total = 1;
    node* root = new node(0);
    node* move = root;
    for(int i = 1; i <= n; i++) {
        total *= i;
        move->next = new node(i);
        move = move->next;
    }
    total /= n;
    string result;
    move = root;
    int f = n - 1;
    for(int i = 1; i <= n && k > 0; i++) {
        cout<<result<<endl;
        while(total < k) {
            move = move->next;
            k -= total;
        }
        result += to_string(move->next->val);
        move->next = move->next->next;
        if(f > 1)
            total /= f--;
        move = root;
    }
    return result;
}