Sharing my 4ms iterative C++ solution

  • 0

    the idea behind is just to choose the number for the ith place of the resulting string;
    it changes every time that k is larger than factorial of the length of the remainder of the string (hope the code clarifies it a bit). I don't like string operations there, maybe there is something a bit more efficient? I tried swapping characters, but it's in fact slower

    class Solution {
            inline int fact(int i){
                //i>=1&& i<=8 (since n<=9)
                static int fact[]={1,2,6,24,120,720,5040,40320};
                return fact[i-1];
            string getPermutation(int n, int k) {
                string s;
                for(int i=0;i<n;++i){
                if(n==1) return s;
                for(int i=0;i<n-1;++i){
                    int remLength=n-1-i; //always at least 1
                    int mod=fact(remLength);
                    int next=k/mod;
                    //s[i+next] is the value we want s[i] to have;
                    //s[i+1] should be what s[i] was, the remaining part should keep ordering
                        char tmp=s[i];
                        s.insert(s.begin()+i+1, tmp);
                return s;

Log in to reply

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