首页 > 代码库 > LeetCode OJ--Permutation Sequence *

LeetCode OJ--Permutation Sequence *

2024-07-08 03:50:58   223人阅读

求第k个排列。

刚开始按照一个排列一个排列的求，超时。

于是演算了一下，发下有数学规律，其实就是康托解码。

 

康托展开：全排列到一个自然数的双射

X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!

ai为整数，并且0<=ai<i(1<=i<=n)

 适用范围：没有重复元素的全排列

 

全排列的解码

如何找出第16个（按字典序的）{1,2,3,4,5}的全排列？

1. 首先用16-1得到15

2. 用15去除4! 得到0余15

3. 用15去除3! 得到2余3

4. 用3去除2! 得到1余1

5. 用1去除1! 得到1余0

有0个数比它小的数是1，所以第一位是1

有2个数比它小的数是3，但1已经在之前出现过了所以是4

有1个数比它小的数是2，但1已经在之前出现过了所以是3

有1个数比它小的数是2，但1,3,4都出现过了所以是5

最后一个数只能是2

所以排列为1 4 3 5 2

 

class Solution{public:    string getPermutation(int n, int k)    {        //get fractial        vector<int> fractial;        fractial.push_back(1);        for(int i = 1;i<n;i++)        {            fractial.push_back(fractial[i-1]*(i+1));        }        //to mark if this digit selected ,true means can be selected, false means already selected.        vector<bool> allnum;        for(int i = 0; i <=n; i++)            allnum.push_back(true);        int ChuShu = k - 1, YuShu = 0;        string ans;        int weishu = 0;        while(weishu<n)        {            int _num_i;            int place;            if(weishu == n-1) // the last digit                _num_i = select(allnum,1);            else            {                YuShu = ChuShu % fractial[n-2-weishu];                place = ChuShu / fractial[n-2-weishu];                                 _num_i = select(allnum,place + 1 );            }            ChuShu = YuShu;            weishu ++;            char ch = ‘3‘ - 3 + _num_i;            ans += ch;        }        return ans;    }    int select(vector<bool> &allnum,int place)    {        int i = 1;                while(place)        {            if(allnum[i] == true)            {                place--;                if(place == 0)                    break;            }            i++;        }        allnum[i] = false;        return i;    }};int main(){    class Solution myS;    cout<<myS.getPermutation(5,16);    return 0;}

 


联系
我们