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

  • 0
    class Solution {
        string getPermutation(int n, int k) {
            int i, j, base=1;
            string s(n, '0');
            for(int i=1; i<=n; 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--;}
            return s;

  • 0

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

  • 0


    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.