首页 > 代码库 > LeetCode: Permutation Sequence [059]

LeetCode: Permutation Sequence [059]

2024-07-06 00:09:31   224人阅读

【题目】


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):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.



【题意】

        数组[1,2,3,4,...n]共有n!中不同的排列，给定整数n和k, 返回n!个有序的排列中的第k个排列


【思路】

       

        由于排列是有序的，我们可以以此缩小搜索第K个排列的范围。
        当第1位确定之后，剩余的n-1个数共有(n-1)!种排列
        当第2位确定之后，剩余的n-2个数共有(n-2)!种排列
        以此类推...
        
        我们就以第一位为例，因为有序，第一位的取值肯定依次取[1,2,3,4,...n]
        第一位为1时，其包含的排列序号范围[1, (n-1)!]
        第一位为2时，其包含的排列序号范围[(n-1)!+1, 2*(n-1)]
        依次类推...
        
        我们只需要看k是在哪个序号范围内的，然后不断确定后续数值以缩小范围即可。


【代码】

class Solution {
public:
    
    int getCaseCount(int n){
        //计算n!
        if(n==0)return 1;
        int result=1;
        for(int i=1; i<=n; i++){
            result*=i;
        }
        return result;
    }
    
    string getPermutation(int n, int k) {
        int size=getCaseCount(n);
        if(k<1 || k>size)return "";
        vector<int>candidates;
        for(int i=1; i<=n; i++)candidates.push_back(i);

        int pos=1;              //当前确定第几位数
        int totalCount=0;       //已经确定了前多少个排列，用于缩小范围
        string result="";
        while(pos<=n){
            size=getCaseCount(n-pos);   //确定当前值
            int index=1;                //当前位置要放candidates集合中的第几个数
            while(totalCount+index*size<k)index++;
            //填写当前数
            result+= (char)(candidates[index-1]+'0');
            //从候选集合中删除当前数
            candidates.erase(candidates.begin()+index-1);;
            //更新范围
            totalCount+=size*(index-1);
            pos++;
        }
        return result;
    }
};


联系
我们