cleanest c++ impl inspired by base conversation alg


  • 0
    B

    the idea is simple, we want to find out the sequence number to its corresponding position at each slot index. this is very similar how base conversation is computed (try to implement a int-to-string alg), the only difference the "base" isn't fixed, it's increasing from 1 to n and the character set is adjusted based on what haven't been used.

    string getPermutation(int n, int k) {
        vector<char> rems(n);
        vector<int> numOfCounts(n);
        k--; // change it to 0 based
        for (char i = 1; i <= n; i++) {
            rems[i - 1] = (i + '0');
            numOfCounts[n - i] = k % i;
            k /= i;
        }
    
        string res;
        for(int index:numOfCounts) {
            res.push_back(rems[index]);
            rems.erase(rems.begin() + index);
        }
        return res;
    }
    

Log in to reply
 

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