Permutation Sequence

Solution 1

一开始我想使用回溯法去实现（逻辑上是可行的），但是空间占用超出限制了。因此查找了官方题解。

官方题解给出方法的核心思路就是：给定序列的字典序是固定的，利用规律计算得到对应的字典序。

对于第 i i i个位置上的数字，已知已经有 i − 1 i - 1 i−1个数字被选中，因此所有的置换排列*有 ( n − i + 1 ) ! (n - i + 1)! (n−i+1)!个方案。所有剩下的数字不同，且每个数字被选中的情况下分别有 ( n − i ) (n - i) (n−i)个方案。

如果要求选出字典序第 k k k个方案，那么这个数字的序号（nMin）应该是 ⌊ ( k − 1 ) / ( n − i ) ! ⌋ + 1 \lfloor (k - 1) / (n - i)! \rfloor + 1 ⌊(k−1)/(n−i)!⌋+1。

确定了这个数字之后，就需要更新下一个数字的序号了，这个序号可以通过计算 ( k − 1 ) mod ⁡ ( n − i ) ! + 1 (k - 1) \operatorname{mod} (n - i)! + 1 (k−1)mod(n−i)!+1。

这个思路实际上和数制转换的思路很相似，但是确实很精巧，以至于我想不到