Sharing my 4ms iterative C++ solution


  • 0
    S

    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];
            }
        public:
            string getPermutation(int n, int k) {
                k-=1;
                string s;
                for(int i=0;i<n;++i){
                    s.push_back('1'+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
        
                    if(next!=0){
                        char tmp=s[i];
                        s[i]=s[i+next];
                        s.erase(s.begin()+i+next);
                        s.insert(s.begin()+i+1, tmp);
                    }
                    k%=mod;
                }
                return s;
            }
        };

Log in to reply
 

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