[recommend for beginners]clean C++ implementation with detailed explanation


  • 0
    class Solution {
    public:
        string getPermutation(int n, int k) {
            int i, j, base=1;
            string s(n, '0');
            for(int i=1; i<=n; i++){
                base*=i;
                s[i-1]+=i; /*** change string s to "12345..." ***/
            }
            /***
             * n=4 k=10  n!=24 
             * i=0 base=6 k=10  s=[2,1,3,4]
             * i=1 base=2 k=4   s=[2,3,1,4]
             * i=2 base=1 k=0   s=[2,3,4,1]
             ***/
            for(i=0, k--; i<n; i++){
                base/=(n-i); /*** f/(n-i) is the i-th base ***/
                j=i+k/base; /*** f/base is the i-th value-index ***/
                char c=s[j];
                /*** move the remained number tegother **/
                while(j>i)  { s[j]=s[j-1]; j--;}
                k%=base;
                s[i]=c;
            }
            return s;
        }
    };

  • 0
    B

    Can you explain in more detail the reasoning behind the implementation and the reasoning for each step?


  • 0

    @benjie

    You can think that for the number start with "1", the rest position have n-1 number, so there are (n-1)! combinations , So we can devide the k by (n-1)! to check the number in the left-most-pos. Similarly .... You get the final result .


Log in to reply
 

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