0ms C++ programme


  • 0
    J

    O(N) time complexity.

      class Solution {
            void swap(int &a,int &b)
            {
                int temp=a;
                a=b;
                b=temp;
            }
        public:
            string getPermutation(int n, int k) {
                string res="";
                int *a=new int [n];
                int *mul=new int [n];
                mul[0]=1;
                for(int i=1;i<n;i++)
                    mul[i]=i*mul[i-1];
                for(int i=0;i<n;i++)
                {
                    a[i]=i+1;
                }
                int j=n-1;
                while(k&&j>0)
                {
                    int head=k/mul[j];
                    if(k%mul[j]==0)head--;
                    k-=head*mul[j];
                    for(int i=n-1-j;i<n-j+head;i++)
                        swap(a[i],a[n-j+head-1]);
                    j--;
                }
                for(int i=0;i<n;i++)
                    res.append(1,a[i]+'0');
                delete []a;
                delete []mul;
                return res;
            }
        };

Log in to reply
 

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