leetcode 60 Permutation Sequence

题目

https://leetcode.com/problems/permutation-sequence/submissions/

思路

直接计算即可,使用 vector 模拟优先级队列,计算当前位置应该是第几大的数 k– 后直接对应下标,不需要考虑向上或向下取整问题

源码

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

发表评论

邮箱地址不会被公开。 必填项已用*标注