首页 > 代码库 > leetcode第一刷_Permutation Sequence

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;
    }
};