0060._Permutation_Sequence.md

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;
    }
};