It's a math problem, C++ solution


  • 1
    class Solution {
    public:
        //TLE - its efficiency is too bad, though it works.
        string getPermutation(int n, int k) {
            vector<int> v;
            for(int i = 1; i <= n; i++) v.push_back(i);
            while(k > 1) {
                int i = n-2, j = n-1;
                while(v[i] > v[i+1]) i--;
                while(v[i] > v[j]) j--;
                swap(v[i], v[j]);
                reverse(v.begin()+i+1, v.end());
                k--;
            }
            string s;
            for(int i = 0; i < n; i++) s += to_string(v[i]);
            return s;
        }
    
        //AC - 0ms - using combination and permutation logics - very terse;
        string getPermutation(int n, int k) {
            int i = 1, j = 0, p = 1;
            string s;
            for(; i <= n; ++i) {
                p *= i; //n!;
                s += char('0'+i); //generate the sequence string as "123...n";
            }
            for(i = 0, k--; i < n; ++i) {
                p /= n-i; //(n-i)!;
                j = i + k/p; //get character for current position i;
                char c = s[j];
                for(; j > i; --j) s[j] = s[j-1]; //shift to the right for one position;
                s[i] = c;
                k %= p; //consider the left sequence;
            }
            return s;
        }
    };
    

Log in to reply
 

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