My C++ solution, easy to understand


  • 0
    S
    class Solution {
    public:
        string getPermutation(int n, int k) {
            int const factorials[] {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
            string nums = "";
            for(int i = 1; i<=n; i++) {
                nums += i + '0';
            }
            if(k > factorials[n]) return nums;
            int k1 = k - 1;
            for(int i = 0; i < n && k1 > 0; i++) {
                int fctrl = factorials[n-i-1];
                rotate(nums, i, i + k1/fctrl);
                k1 = k1 % fctrl;
            }
            return nums;
        }
    private:
        void rotate(string & nums, int i, int j) {
            int tmp = nums[j];
            for(int k = j-1; k >= i; k--) {
                nums[k+1] = nums[k];
            }
            nums[i] = tmp;
        }
    };
    

Log in to reply
 

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