leetcode || 60、Permutation Sequence

problem:

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 (ie, 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.

Hide Tags   Backtracking Math 題意：指定一個n位起始數，輸出第k個下一個排列組合

thinking:

（1）直覺想到調用next_permutation()函數，該函數STL已經實作，我自己也實作過（http://blog.csdn.net/hustyangju/article/details/44751293），因為next_permutation()函數的時間複雜度為O（n），是以調用該函數的時間複雜度為O（n*k），相當龐大，送出Time Limit Exceeded

（2）math 法

注意到排列組合的規律： n! = n*(n-1)!

将數組array[n] ={1,2,...,n}  ，輸出序列的第一位數字在array的下标index1等于？

index1 = (k-1)/n!    

開始考慮第二位數字：

首先：k%=n!

index2 =  k/(n-1)!

....

以此類推，直到求出第n位數字的下标indexn

（3）DFS法

視決定一位數字為 1 step，深度為n，每一步确定數字的方法同 方法2，是以DFS也很容易實作

code:

math法：

Accepted

4 ms

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> tmp;
        int count=1;
        string str;
        k--;
        for(int i=1;i<=n;i++)
        {
            tmp.push_back(i);
            count*=i;
        }
        for(int i = 0 ; i < n; i++)
        {
            vector<int>::iterator it=tmp.begin();
            count = count/(n-i);
            int selected = k / count;
            k%=count;
            str.push_back('0' + tmp[selected]);
            tmp.erase(it+selected);
        }
        return str;
     
    }

};
           

DFS法：

Accepted

4 ms

class Solution {
private:
    string str;
public:
    string getPermutation(int n, int k) {
        vector<int> tmp;
        str.clear();
        int count=1;
        k--;
        for(int i=1;i<=n;i++)
        {
            tmp.push_back(i);
            count*=i;
        }
        dfs(0,n,tmp,k,count);
        return str;
    }
protected:
    void dfs(int dep,int n,vector<int> &tmp, int &k,int &count)
    {
        if(dep>=n)
            return;
        vector<int>::iterator it=tmp.begin();
        count/=n-dep;
        int index=k/count;
        k%=count;
        str.push_back('0' + tmp[index]);
        tmp.erase(it+index);
        dfs(dep+1,n,tmp,k,count);
    }

};