首页 > 代码库 > LeetCode "Permutation Sequence"

LeetCode "Permutation Sequence"

1A! This is actually a basic question in Combinatorics: if at digit[k] = n, it contributes (k-1)! * n to the targeted index.

class Solution {public:    unsigned long long nPrime(unsigned n)    {        if (n == 1) return 1;        return n * nPrime(n - 1);    }    string getPermutation(int n, int k) {        if (n == 1) return "1";        unsigned long long nbase = nPrime(n - 1);        k--;                //    Record counts        vector<int> inx;        for (int i = n; i >= 1; i--)        {            int currInx = k / nbase;            inx.push_back(currInx);            k -= nbase * currInx;            if(nbase > 1) nbase /= (i - 1);        }        //    Recover digits                string ret;        unordered_set<int> mark;        for (int i = 0; i < inx.size(); i++)        {            int currInx = inx[i];            int k;            for (k = 0; k < 9 && currInx >= 0; k ++)            {                if (mark.find(k) == mark.end()) currInx--;            }            ret += 0 + k;            mark.insert(k - 1);        }        return ret;    }};