leetcode:Permutation Sequence (顺序排列第k个序列)

题目：

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):

"123"

"132"

"213"

"231"

"312"

"321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

题意1~n组成的序列从小到大排列，按顺序找出第k个序列输出。

开始暴力搞了一下果然超时了，n=9时的时候n！复杂度太大了。

之后认真算了一下发现是有规律的，已知n的值，学过排列组合知道共有n！种排列。

第一位每个数字开头的序列都有（n-1）！个序列，因此n个数字所以共有n！个序列。

以此类推，第二位每一个数开头都有（n-2）！个序列。

因为数字不能重复，我用sign记录数字是否使用过，data存阶层的值。

每次循环找到没使用过的数中第k/data[i]个数就是当前位的数字。

class Solution {  
public:  
    string getPermutation(int n, int k) {  
        int i,j,data[10],sign[10];  
        data[1]=1;  
        for(i=2;i<=n;++i)data[i]=data[i-1]*i;  
        memset(sign,0,sizeof(sign));  
        string s="";  
        i-=2;  
        --k;  
        while(i>=0)  
        {  
            int temp=k/data[i];  
            for(j=1;j<10;++j)  
            {  
                if(sign[j]==0)temp--;  
                if(temp<0)break;  
            }  
            sign[j]=1;  
            s+=j+'0';  
            k%=data[i];  
            i--;  
        }  
        return s;  
    }  
};  
// http://blog.csdn.net/havenoidea

补充：综合编程 , 其他综合 ,