本文共 1847 字，大约阅读时间需要 6 分钟。

题目描述

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

“123”

“132” “213” “231” “312” “321” 给定 n 和 k，返回第 k 个排列。

示例 1：

输入：n = 3, k = 3

输出：“213”

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/permutation-sequence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 C++ 一看就类似 leetcode 46题 全排列，我就用回溯，然后完美超时，，，超时代码：

class Solution {
   public: /*   回溯：因为这是一个全排列的树，没有重复元素，并且选择策略非常明显， */    vector
   
     res;    string getPermutation(int n, int k) {
           string track; //路径        traverse(track,n);        return res[k-1];    }    void traverse(string &track,int n){
           //结束条件        if(track.size()==n){
               res.push_back(track);            return;        }        for(int i=1;i<=n;i++){
                  char c=i+'0';            if(find(track.begin(),track.end(),c)!=track.end())                continue;  //已经选过的，就不选            //选择                     track.push_back(c);            traverse(track,n);            track.pop_back(); //回溯        }                }};
   

优化…

估计要要用到数学知识…

class Solution {
   public: /*   优化。。。   数学知识。。   先找第K个排列的首位：        index=K/(n-1)！        K%(n-1)！ ==0, 开头第一位是 index                  !=0， 开头第一位是inde=index+1        找第二位，K=k-index*(n-1)!        同上。。。 */    string getPermutation(int n, int k) {
           string res;        vector
   
     candidates; //候选数字        //求1-n的阶乘        vector
    
      factorial(n+1);        factorial[0]=1;        int fact=1;        for(int i=1;i<=n;i++){
               candidates.push_back(i);            fact*=i;            factorial[i]=fact;        }                k-=1;        for(int i=n-1;i>=0;i--){
               //计算候选数字的index            int index=k/factorial[i];            k-=index*factorial[i];            res.push_back(candidates[index]+'0');            candidates.erase(candidates.begin()+index);        }        return res;    }};