0060. Permutation Sequence ========================== 题目信息 -------- :题号: 0060. 第 k 个排列 :难度: Hard :主题: 排列、字典序、阶乘分组、秩选择 :原题: `LeetCode 0060 `_ :重点: 从按字典序访问排列树,推导到用阶乘块直接选择每一位 题目重述 -------- 数字 ``1`` 到 ``n`` 各使用一次,可以形成 ``n!`` 个排列。把这些排列按字典序从小到大编号为 ``1..n!``,返回第 ``k`` 个排列对应的字符串。 约束为 ``1 <= n <= 9``、``1 <= k <= n!``。 自建示例 -------- .. code-block:: text 输入:n = 5, k = 42 输出:"24531" 以同一个首位开头的排列共有 ``4! = 24`` 个。第 42 个排列跳过以 1 开头的 24 个排列,进入以 2 开头的 分块;继续在更小的阶乘块中定位,最终得到 ``"24531"``。 .. code-block:: text 输入:n = 4, k = 17 输出:"3412" 每个首位分块包含 ``3! = 6`` 个排列,第 17 个排列位于第三块,因此首位是 3。 .. code-block:: text 输入:n = 3, k = 6 输出:"321" 最后一个字典序排列是全部数字降序排列。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: bool findByEnumeration( int n, int& remainingRank, std::vector& used, std::string& current, std::string& answer ) { if (static_cast(current.size()) == n) { --remainingRank; if (remainingRank == 0) { answer = current; return true; } return false; } for (int value = 1; value <= n; ++value) { if (used[value]) continue; used[value] = true; current.push_back(static_cast('0' + value)); if (findByEnumeration( n, remainingRank, used, current, answer )) { return true; } current.pop_back(); used[value] = false; } return false; } std::string enumerateLexicographically(int n, int k) { std::vector used(n + 1, false); std::string current; std::string answer; findByEnumeration(n, k, used, current, answer); return answer; } std::string selectByFactorialBlocks(int n, int k) { std::vector factorial(n + 1, 1); for (int value = 1; value <= n; ++value) { factorial[value] = factorial[value - 1] * value; } std::vector available; for (int value = 1; value <= n; ++value) { available.push_back(value); } int rank = k - 1; std::string result; result.reserve(n); for (int remaining = n; remaining >= 1; --remaining) { const int blockSize = factorial[remaining - 1]; const int choice = rank / blockSize; rank %= blockSize; result.push_back( static_cast('0' + available[choice]) ); available.erase(available.begin() + choice); } return result; } public: std::string getPermutation(int n, int k) { return selectByFactorialBlocks(n, k); } }; 题解 ---- 排列树基线 ~~~~~~~~~~ 从空前缀开始,每一层按从小到大的顺序选择一个未使用数字。候选顺序固定为升序,因此搜索树叶子的访问顺序 就是排列的字典序。 ``enumerateLexicographically`` 到达叶子时把剩余名次减一,第一次减到零的叶子就是答案。它不保存全部排列, 但目标若靠后,仍需访问接近 ``n!`` 个叶子。重复工作集中在整棵与目标无关的子树中。 阶乘分块 ~~~~~~~~ 当前还有 ``remaining`` 个数字时,固定下一位后,剩余 ``remaining - 1`` 个数字可以任意排列,所以每个候选 对应的子树大小都是: .. code-block:: text blockSize = (remaining - 1)! 候选数字按升序排列,这些等大的子树也按字典序连续排列。于是无需逐个访问叶子,只需确定目标位于第几个 阶乘块,再进入该块继续定位。 零基秩 ~~~~~~ 题目名次从 1 开始,数组下标与块编号从 0 开始。先转换为: .. code-block:: text rank = k - 1 当前位的选择与块内新秩为: .. code-block:: text choice = rank / blockSize rank = rank % blockSize ``choice`` 表示跳过多少个完整块,也就是当前选择 ``available[choice]``。先减一能够正确处理块边界;例如 块大小为 6 时,第 6 个排列的零基秩是 5,仍属于第 0 块。 阶乘秩选择不变量 ~~~~~~~~~~~~~~~~ 每轮开始时,保持以下状态: .. code-block:: text available 按升序保存尚未使用的 remaining 个数字 result 是目标排列已经确定的前缀 0 <= rank < remaining! 因为: .. code-block:: text remaining! = remaining * (remaining - 1)! 所以 ``choice = rank / blockSize`` 一定满足 ``0 <= choice < remaining``,能够安全索引当前候选数组。 选择该数字后,算法跳过 ``choice`` 个完整子树,并进入唯一包含目标的子树。 更新 ``rank %= blockSize`` 后,有: .. code-block:: text 0 <= rank < (remaining - 1)! 这正是下一轮需要的秩范围。已选数字从 ``available`` 中删除后,每个数字只会使用一次,剩余候选仍保持升序, 下一层的数组下标继续对应字典序块编号。 当 ``remaining`` 递减到零时,每轮都进入了唯一包含原目标的子树,最终留下的叶子恰好是第 ``k`` 个排列。 状态演化 ~~~~~~~~ 对 ``n = 5``、``k = 42``,初始零基秩为 ``41``: .. list-table:: :header-rows: 1 * - 可用数字 - ``rank`` - 每块大小 - ``choice`` - 选择结果 * - ``[1,2,3,4,5]`` - 41 - ``4! = 24`` - 1 - 选择 2,块内秩 17 * - ``[1,3,4,5]`` - 17 - ``3! = 6`` - 2 - 选择 4,块内秩 5 * - ``[1,3,5]`` - 5 - ``2! = 2`` - 2 - 选择 5,块内秩 1 * - ``[1,3]`` - 1 - ``1! = 1`` - 1 - 选择 3,块内秩 0 * - ``[1]`` - 0 - ``0! = 1`` - 0 - 选择 1 依次得到 ``2、4、5、3、1``,答案为 ``"24531"``。 两种方法的关系 ~~~~~~~~~~~~~~ 回溯法按字典序逐个访问排列树叶子。阶乘分块法使用每棵子树的精确叶子数,一次跳过整棵无关子树。 两者访问的是同一棵排列树,优化点只是把逐叶计数替换为按子树规模直接定位。 边界处理 ~~~~~~~~ ``k = 1`` 时,``rank = 0``,每轮都选择最小可用数字,得到 ``123...n``。 ``k = n!`` 时,零基秩为 ``n! - 1``,每轮都选择最大可用数字,得到降序排列。 题目限制 ``n <= 9``,因此 ``9! = 362880`` 可以安全存入 ``int``,数字 1 到 9 也都能用单个字符表示。 复杂度分析 ~~~~~~~~~~ 按字典序回溯最坏需要访问 ``O(n!)`` 个排列,递归路径与辅助标记使用 ``O(n)`` 空间。 阶乘分组执行 ``n`` 轮选择。``vector::erase`` 删除中间元素时需要移动后缀,单轮最坏 ``O(n)``,总时间为 ``O(n²)``;阶乘数组、候选数组与结果使用 ``O(n)`` 空间。主入口调用 ``selectByFactorialBlocks``。