Sharing my straightforward C++ solution with explanation


  • 34
    Z
    string getPermutation(int n, int k) {
        int pTable[10] = {1};
        for(int i = 1; i <= 9; i++){
            pTable[i] = i * pTable[i - 1];
        }
        string result;
        vector<char> numSet;
        numSet.push_back('1');
        numSet.push_back('2');
        numSet.push_back('3');
        numSet.push_back('4');
        numSet.push_back('5');
        numSet.push_back('6');
        numSet.push_back('7');
        numSet.push_back('8');
        numSet.push_back('9');
        while(n > 0){
            int temp = (k - 1) / pTable[n - 1];
            result += numSet[temp];
            numSet.erase(numSet.begin() + temp);
            k = k - temp * pTable[n - 1];
            n--;
        }
        return result;
    }
    

    In this program, pTable refers to permutation table and numSet refers to a set of numbers from 1 to 9. Before while loop, we need to initialize pTable and numSet, which is trivial.

    In while loop, we do these following things.

    1 calculate which number we will use.

    2 remove that number from numSet.

    3 recalculate k.

    4 n--.

    Finally, we return result.


  • 0
    C

    This is an amazing solution! How do you come up with this one ? Mine is not that elegant.


  • 1
    Z

    For this problem, you can start with several simple examples, like 123 and 1234. It's easier to find a pattern from them. Then think about general situation. Good luck :)


  • 0
    C

    Thank you for your advice!


  • 0
    Z

    No problem :)


  • 1
    W

    I would like to make the code more concise for your reference.

    First, the pTable array is redundant. We could just use a int value, like factorial, and recalculating it in the loop by factorial /= n;. While its ok to use pTable because n is no more than 9.

    Second, I think sentence vector<char> numSet; can be modified to vector<int> numSet, thus we could initialize it using:

    for (int idx = 1; idx <=n; ++idx) {
        numSet.push_back(idx);
    }
    

    here, result += numSet[temp]; can be result += '0' + numSet[temp];

    Then, the way recalculating the k makes me confused at first sight. I think it can be more clear by using k %= pTable[n - 1]; which means the remain permutations.

    Thx.


  • 1

    I think your algorithm is O(n^2), not O(n). Because each time you call vector<T>::erase(it), the time complexity is O(n), and you call it n times. So your time complexity is O(n^2).


  • 0
    S
    This post is deleted!

  • 4
    S

    it's not necessary to use push_back() to initialize the numSet. In C++11, which is supported by LeetCode, there's an easy way like this :
    vector<char> numSet{'1', '2', '3', '4', '5', '6', '7', '8', '9'};


  • 2
    O

    Very nice solution!

    Just want to make it a bit more concise.

    Also, handle the case if k > n!

    class Solution {
    public:
        string getPermutation(int n, int k) {
            int pTable[10] = {1};        //factorial pre-calculated
            for(int i = 1; i < 10; i++)  pTable[i] = i * pTable[i-1];
            
            vector<char> numSet;         //in-order num set to fetch numbers
            for(int i = 0; i < n; i++) numSet.push_back('0'+i+1);
            
            string ans = "";
            int k1 = (k-1) % pTable[n];  //if k > n!. (k-1) for zero-based index
            int n1 = n;
            
            while(n1 > 0) {
                int numPermutation = k1 / pTable[n1-1];
                ans += numSet[numPermutation];
                numSet.erase(numSet.begin()+numPermutation);
                k1 %= pTable[n1-1];
                n1--;
            }
            return ans;
        }
    }

  • 0
    E

    We don't always need 9 digits, get n digits for numSet.
    And, save some space of pTable.

    class Solution {
    public:
        string getPermutation(int n, int k) {
            int pTable = n, temp;
            vector<char> numSet(n, '1');
            for(int i = 1; i < n; i++){
                pTable *= i;
                numSet[i] = numSet[i-1] + 1;
            }
            string res;
            while( n > 0 ){
                pTable /= n;
                temp = (k-1)/pTable;
                res += numSet[temp];
                numSet.erase(numSet.begin() + temp);
                k -= temp * pTable;
                n--;
            }
            return res;
        }
    };
    

  • 0
    M

    A version based off of @zxyperfect :

    string getPermutation(int n, int k)
    {
        const int fact[10] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
    
        char seq[] = "123456789";
        char res[] = "000000000";
    
        for (int i = 1; i <= n; ++i)
        {
            // find index and copy the corresponding digit to the result
            auto idx = (k - 1) / fact[n - i];
            res[i - 1] = seq[idx];
    
            // erase seq[idx] by writing over it
            for (int j = idx; j < n; ++j)
                seq[j] = seq[j + 1];
    
            // reduce k
            k -= idx * fact[n - i];
        }
    
        return string(res, res + n);
    }
    

  • 0
    K

    The erase() function of vector will always create a new vector array and copy the original value to it except the erased one. So the time complexity is O(n^2).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.