Skip to content

60. Permutation Sequence

难度:Medium

刷题内容

原题连接

  • https://leetcode.com/problems/permutation-sequence/

内容描述

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:

Input: n = 3, k = 3
Output: "213"
Example 2:

Input: n = 4, k = 9
Output: "2314"

˼·1 **- ʱ¼ä¸´ÔÓ¶È: O(n^2)*- ¿Õ¼ä¸´ÔÓ¶È: O(n)***

ÏȽ«ËùÓÐÊý°´Ë³Ðò´æÔÚÓиö×Ö·û´®ÖУ¬È»ºóÑ­»·n´Î£¬Ã¿´ÎÕÒµ½ÕýÈ·µÄÊý£¬ÓÉÓÚearseʱ¼ä¸´ÔÓ¶ÈΪn£¬ËùÒÔ×ܵÄʱ¼ä¸´ÔÓ¶ÈΪn^2

class Solution {
public:
    string getPermutation(int n, int k){
        int arr[n + 1];
        string ans,org;
        for(int i = 1;i <= n;++i)
        {
            org.push_back(i + '0');
            i == 1 ? arr[i] = 1 : arr[i] = arr[i - 1] * i;
        }
        for(int i = n - 1;i > 0;--i)
        {
            int t = k / arr[i];
            cout<< t<< endl;
            k = (k) % arr[i];
            if(!k)
            {
                k = arr[i];
                t--;
            }
            ans.push_back(org[t]);
            org.erase(org.begin() + t);
            arr[i] = 0;
        }
        ans.push_back(org[0]);
        return ans;
    }
};


回到顶部