LeetCode: Permutation Sequence

思路分析

非常经典的排列问题。传统的暴力做法显然会超时，我们需要思考这道题目背后的数学规律。要求一串序列的任意第k个排列，显然不存在O(1)的算法能够一次推出。这样我们考虑能否一位一位地推出整个序列呢？显然我们可以得到规律，设第一位是第m个数字，则应该有：m=upper(k/(n-1)!)。这样，为了产生这样的第一位，我们消耗了多少次next_permutation呢？应该消耗了(m-1)*(n-1)!次。这样，问题就转化为对于除掉第一位后剩余的序列，求其第k-(m-1)*(n-1)!个排列。这样，问题就可以递归求解了。当然，这个递归可以轻易转换为循环，因为它本质上是尾递归。

代码

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class Solution {
public:
    string getPermutation(int n, int k) {
        string res(n, '0');
        int nums[10], fracs[10];
        int frac = 1;
        rep(i, n) {
            if ( i ) frac *= i;
            fracs[n - i - 1] = frac;
            nums[i] = i + 1;
        }
        rep(i, n) {
            int pos = (k - 1) / fracs[i];
            res[i] = nums[pos] + '0';
            REP(j, pos, n - i) nums[j] = nums[j + 1];
            k -= pos * fracs[i];
        }
        return res;
    }
};