LeetCode 0060 - Permutation Sequence

Reck Zhang

发布于 2021-08-11 10:40:25

2900

发布于 2021-08-11 10:40:25

文章被收录于专栏：Reck Zhang

Permutation Sequence

Desicription

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 (ie, 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.

Solution

class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        vector<int> nums(n), f(n);
        for (int i=0; i<n; i++) nums[i]=i+1;
        f[0]=1;
        for (int i=1; i<n; i++) f[i]=f[i-1]*i;
        
        k--;
        for (int i=n-1; i>=0; i--) {
            int j=k/f[i];
            res+=nums[j]+'0';
            nums.erase(nums.begin()+j);
            k%=f[i];
        }
        return res;
     }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-11-13，如有侵权请联系 cloudcommunity@tencent.com 删除

contains