LC60 Permutation Sequence

本题链接：Permutation Sequence

本题标签：Math, Backtracking

本题难度：

英文题目 中文题目

---

方案1： 利用 Next Permutation 代码

class Solution {
private:
    void nextPermutation(vector<int>& nums) {
        if(nums.empty() || nums.size() == 1)
            return;
        
        int left = -1, right = -1;
        for(int i = nums.size() - 2; i >= 0; --i)
        {
            if(nums[i] < nums[i+1])
            {
                left = i;
                break;
            }
        }
        if(left == -1)
        {
            reverse(nums.begin(), nums.end());
            return;
        }
            
        for(int i = nums.size() - 1; i > left; --i)
        {
            if(nums[i] > nums[left])
            {
                right = i;
                break;
            }
        }
        swap(nums[left], nums[right]);
        reverse(nums.begin() + left + 1, nums.end());
    }
public:
    string getPermutation(int n, int k) {
        string res;
        vector<int> nums;
        for(int i = 1; i <= n; ++i)
            nums.push_back(i);
        
        for(int j = 1; j < k; ++j)
            nextPermutation(nums);
        
        for(auto n : nums)
            res.push_back(n + '0');
        return res;
    }
};

时间复杂度：

空间复杂度：

---

方案2： 根据观察得到的数学规律

Permutation	Index	k
“123”	0	1
“132”	1	2
“213”	2	3
“231”	3	4
“312”	4	5
“321”	5	6

我们可以看到当n = 3时，总共有6种排列情况。而且这6种情况又可以分为首位数字为1、2、3这3种类别，每种类别各有2种。换句话说，当我们把首位数字固定之后，剩余2位数字的排列就是2！= 2种情况。
然后当k = 3时，即选择第三种排列“213”时，我们可以发现这种情况属于首位数字为2的类别。而首位数字为2这种类别对应的下标Index范围为[2, 3]。所以为了找到这个数字2，我们需要找出对应的数学公式。
我们先构造一个从1到n的数组nums：

index	0	1	2
nums	1	2	3

然后我们根据观察可以发现，首位数字2对应的下标index为1，这可以通过 (k - 1) / (n - 1)! = (3 - 1) / (3 - 1)! = 2 / 2 = 1 算出。这里 k - 1 就是 Index 对应的数字，(n - 1)! 就是剩余2位数字的排列情况。
这样找到首位数字2之后，就将其从nums中删除，得到新nums数组：

index	0	1
nums	1	3

接下来，为了找到第二位数字1，我们需要先将k减去首位数字小于2的情况，即 k = k - (n - 1)! * index = 3 - 2 * 1 = 1。这样就排除了其他不正确的情况。此时第二位数字1的index为0，可以通过 (k - 1) / (n - 2)! = (1 - 1) / (3 - 2)! = 0 / 1 = 0 算出。这里 (n - 2)! 代表固定第二位数字后，剩余1位数字的排列情况。然后再将第二位数字1从nums中删除，剩下的数字以此类推。

class Solution {
private:
    vector<int> calFactorial(int n)  // 计算阶乘的函数
    {
        vector<int> fac;
        fac.push_back(1);
        for(int i = 1; i <= n; ++i)
            fac.push_back(i * fac.back());
        return fac;
    }
public:
    string getPermutation(int n, int k) {
        vector<int> nums;
        for(int i = 1; i <= n; ++i)
            nums.push_back(i);
        
        vector<int> fact = calFactorial(n);
        string res;
        for(int i = 0; i < n; ++i)
        {
            int fac = fact[n - i - 1];
            int index = (k - 1) / fac;  // k - 1是关键点
            res.push_back('0' + nums[index]);
            nums.erase(nums.begin() + index);
            k = k - index * fac;
        }
        return res;
    }
};

时间复杂度：，从nums数组中删除元素，共执行次数为：

空间复杂度：