题目链接https://leetcode-cn.com/problems/permutation-sequence/

题目分析

这个题目还是比较好做的,我思考了不长时间就想到问题的解决办法并一次性AC,但是代码写的太烂。。。

给出n个元素的集合,其所有元素共有 n! 种排列,当我们由小到大找第其第K个排列方式时,我们可以这样办:

先固定第一个数,那么剩下的数就有 (n - 1 )!种排列,根据第一个数的不同可以分为n组,其下标范围为

$$ { [ 0, (n - 1)! ), [(n - 1)!, 2*(n-1)!), ... , [(n-1)*(n-1)!, n!)} $$

我们可以根据每一组的下标范围以及所要查找的第K个排列就可以明确知道它是归于哪一个组。

其实问题到这里就已经解决了,无非是一个递归问题,我们通过不断细化分组,将K定位于某一个组上,这样答案就得出来了。

代码

// 60. 第k个排列 第一次

class Solution {
public:
    stringstream result;
    string getPermutation(int n, int k) {
        vector<int> stack;
        vector<int> allnumber;
        for (int i = 0 ; i < n ; ++i){
            allnumber.push_back(i+1);
        }
        int total = mul(n);
        solve(n, k-1, stack,allnumber, 0, total );
        return this->result.str();
    }

    int mul(int num){
        if (num == 0)
        return 1;
        int res = 1;
        do{
            res *= num--;
        }while(num > 1);
        return res;
    }

    void solve(int n, int k, vector<int> stack , vector<int> remain, int left, int right){
        if (remain.size() == 0){
            for (int i = 0 ; i < stack.size() ; i ++){
                this->result << stack[i];
            }
            return;
        }
        int layerNum  = right - left;
        int part = layerNum / n; 
        for (int i = 0 ; i < n; ++i){
            // TODO 写的太烂 直接 (k - left) / part 多好
            if ( k >= part * i + left && k < part * (i + 1) + left){
                stack.push_back( remain[i]);
                remain.erase(remain.begin() + i);
                solve(n-1, k, stack,remain, part * i  + left,  part * (i + 1) + left );
            }
        }
    }

};

尽管这个方法并不是最优雅的解,但是思路相比其他方法相对比较清晰,原理也比较简单。