leetcode第一刷_Permutation Sequence

這道題還挺好的，如果你的思路是每次生成一個全排列，然後累計到k次，那麼停下來吧，肯定超時了親。。

微軟今年的筆試題裡有一道類似的，我之前已經提到過了，是只有0和1的字符串，求第k個排列是什麼樣子的。這道題比那個要難一些，但是總體的思路是一樣的。假設有n個數要組成排列，求第k個排列。像填表一樣，從高位往地位，逐個填寫。先考慮有n-1個數要組成排列，最多有（n-1)!種情況，當第n個數加入後，第n個數可以是從1增加到n的，沒增加1，所包含的全排列數就會增加（n-1)!，因此，如果用k/（n-1）!，得到的就是第高位排列應該出現的數字。為了計算後面的位應該填什麼，k要更新為k%(n-1)!。計算第i位應該填的是k/(i-1)!。不，不僅僅是這樣，這裡應該是這道題和01串那道題一個很大的不同之處，在填第i位的時候，還要看剩下了哪些數字，應該在剩下的那些數字裡找第k/(i-1)!個。

代碼裡為什麼要先對k減1，用簡單的例子就能理解。就像在一個矩陣中，給了矩陣中的第k個數，要求它對應矩陣中的那個位置，也會先對他減一的。題目中給出了所參與排列數的取值范圍，因此可以先把階乘算出來，放到數組裡。

class Solution {
public:
    string getPermutation(int n, int k) {
        int fac[10];
        bool vis[10];
        memset(vis, 0, sizeof(vis));
        fac[0] = 1;
        for(int i=1;i<10;i++)
            fac[i] = fac[i-1]*i;
        string res(n, '0');
        --k;
        for(int i=n-1;i>=0;i--){
            int temp = k/fac[i];
            int j=1;
            for(;j<10;j++){
                if(vis[j] == 0)
                    temp--;
                if(temp<0)
                    break;
            }
            res[n-i-1] = '0'+j;
            vis[j] = 1;
            k%=fac[i];
        }
        return res;
    }
};