leetcode：60. 排列序列

题目

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

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

给定 n 和 k，返回第 k 个排列。

示例：

输入：n = 3, k = 3
输出："213"

输入：n = 4, k = 9
输出："2314"

输入：n = 3, k = 1
输出："123"

提示：

• 1 <= n <= 9
• 1 <= k <= n!

解答 & 代码

对于 n 个元素的排列，假设第 k 个排列（即本题所求的结果）为
首先要确定第一个元素的值，有 1, 2, …, n 这 n 种取值，对于每个取值作为，都有 (n-1)! 种排列，因此
同理，确定了后，再依次确定, ……
假设当前要确定元素：

• 说明前面的 i 个元素已经确定，还剩 n - i 个数未被使用，可以作为的取值，而每个取值都有 (n - i - 1) 种排列，因此是第个未使用的数（数值要 + 1）
• 确定了后，k 取余数

在实际的代码中，可以首先将 k 的值减少 1，这样可以减少运算，降低代码出错的概率：

1. 是剩余未使用的数中的第个数（数值要 +1）

2. 

   class Solution {
   public:
    string getPermutation(int n, int k) {
        int factorial = 1;                // 阶乘
        for(int i = 1; i < n; ++i)
            factorial *= i;                // 初始化为 (n-1)!
        vector<bool> used(n, false);    // 标记每个数字是否已被使用
        string result(n, ' ');            // 结果
        k -= 1;                            // k 先减 1（相当于从 0 开始编号，避免出错）
        // 确定每一位
        for(int i = 0; i < n; ++i)
        {
            // ai 是剩余未使用的数中的第 order=k/(n-i-1)! 个数
            int order = k / factorial;
            for(int j = 0; j < n; ++j)    // 找第 order=k/(n-i-1)! 个未使用的数
            {
                if(used[j] == false && order == 0)
                {
                    result[i] = '0' + j + 1;    // 数值要 +1（因为从 0 开始记）
                    used[j] = true;                // 标记为已使用
                    break;
                }
                else if(used[j] == false)
                    --order;
            }
            if(i != n - 1)    // 注意这个条件，避免 factorial 的除数为 0
            {
                k = k % factorial;                        // 更新 k 的取值
                factorial = factorial / (n - i - 1);    // 更新阶乘
            }
        }
        return result;
    }
   };

   复杂度分析：

• 时间复杂度：
• 空间复杂度 O(n)：

执行结果：

执行结果：通过
执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了 67.72% 的用户