描述

一个序列[1, 2, 3, 4, ..., n]一共有n!个排列，写一个算法计算第k个排列；

分析

直观的方式是在上一题目中的解法基础上计算1-k-1的序列，以此推导出第k个序列的排列，这么做很浪费时间。

要使用时间复杂度的算法，需要了解康托展开，公式如下：

X = $a_n$ *(n-1)! + $a_(n-1)$ *(n-2)! + $a_1$ *0!

康托展开是一个全排列和一个自然数的双射。

$a_i$ 是一个整数，0<= $a_i$ <n，1<=i<=n；

$a_i$ 表示原数的第i位在当前未出现的元素中是排在第几个

以上公式是根据序列计算序列在全排列中的次序。

假设序列[ $a_1$ , $a_2$ , .... $a_n$ ]，如何计算 $a_1$ 在第一个序列（1, 2, 3...n）中的位置呢？

$a_1$ 之后又n-1个元素，共有(n-1)!个排列，于是就知道：

$a_1$ = k/(n-1)!
$k_2$ = k%(n-1)!; $a_2$ = $k_2$ /(n-2)!
$a_n$ = 0

根据以上分析可以得出代码：

int factorial(int n) {
    int result = 1;
    for(int i=1; i<=n; i++) {
        result *= i;
    }
    
    return result;
}

vector<int> kthPermutation(const vector<int>&num, int k)
{
    int n = num.size();
    vector<int> S(num);
    vector<int> result;
    
    int base = factorial(n - 1);
    --k;
    
    for (int i=n-1; i>0; k%=base, base/=i, --i) {
        auto a = next(S.begin(), k/base);
        result.push_back(*a);
        S.erase(a);
    }
    
    result.push_back(S[0]);
    
    return result;
}

此算法的时间复杂度为O(n)，空间复杂度为O(1)。

代码在这儿