How can I improve the code not to get TLE?


  • 0
    H

    really could not think of better solution, thanks!

      class Solution {
        public:
            string getPermutation(int n, int k) {
                string s;
                for(int i=0;i<n;i++)
                {
                    s.push_back('1'+i);
                }
                int count =1;
                while(count<k && nextPermutation(s, n))
                    count++;
                if(count<k) return string();
                return s;
            }
            bool nextPermutation(string &s, int n) {
                if(n<=1) return false;
                
                int i=n-1;
                while(i>0 && s[i]<=s[i-1])
                    i--;
                if(i<=0)
                {           
                    return false;
                }
                else
                {
                    for(int j=n-1;j>=i;j--)
                    {
                        if(s[j]>s[i-1])
                        {
                            swap(s[i-1],s[j]);
                            reverse(s, i, n-1);
                            return true;
                        }
                    }
                }
            }
            
            void reverse(string &v, int start, int end)
            {
                while(start<end)
                {
                    swap(v[start], v[end]);
                    start++; end--;
                }
            }
        };

Log in to reply
 

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