排列序列 图解题解

这道题到底在问什么

n, k

4, 9

输出

"2314"

为何

所有排列里第 9 个就是 2314

先想最直接的笨办法

笨办法是真把排列一个个列出来数到第 9 个。n 一大(比如 n=9 有 36 万个),数到 k 会慢到爆,我们要更聪明的办法。（动画第 3 步）

最优解：一步一步想明白

1. 3笨办法是真把排列一个个列出来数到第 9 个。n 一大(比如 n=9 有 36 万个),数到 k 会慢到爆,我们要更聪明的办法。
2. 4n=4 时,第一位是 1 的排列有 3!=6 个、第一位是 2 的也有 6 个……排列被切成每块 6 个的整齐区块。这就是不用一个个数的突破口。
3. 5k=9 落在第 2 块把 24 个排列按首位分成 4 块、每块 6 个。k=9 落在「首位为 2」这一块里——所以答案第一位必是 2。我们用除法直接算出在第几块。
4. 6把 k 减 1 变成从 0 数起的下标,除以块大小得到「取第几个数」,取余得到「在块内的新排名」。下面用 n=4,k=9 一位一位演给你看。
5. 7k=9,待定 4 位这排格子是候选数字池 [1,2,3,4],谁被取走就变灰。先把 k 减 1 变成 8(从 0 数起)。准备定第 1 位。
6. 8剩 4 个 → 块大小 = 3!定第 1 位时,后面还剩 3 个数自由排,每块有 3! = 6 个排列。拿 8 去除以 6,看落在第几块。
7. 9取候选池第 1 个 → 28 ÷ 6 = 1(整除),所以取候选池下标 1 的数,也就是 2。紫框指着它——第 1 位定为 2。
8. 10答案 = "2"把 2 取走拼进答案,这格变灰封存(不再参与)。候选池实际只剩 [1,3,4]。答案现在是 "2"。
9. 11k 缩小到块内8 ÷ 6 余 2,把 k 更新成 2——意思是「在首位为 2 的这 6 个排列里,我要第 2 个(从 0 起)」。继续定第 2 位。
10. 12剩 3 个 → 块大小 = 2!定第 2 位时,候选池(灰掉 2 后)剩 1、3、4 共 3 个,每块 2! = 2 个排列。拿 k=2 去除以 2。
11. 13取剩余里第 1 个 → 32 ÷ 2 = 1,取剩余候选 [1,3,4] 里下标 1 的数。1 是第 0 个、3 是第 1 个——所以第 2 位是 3。注意是在没被灰掉的数里数。
12. 14答案 = "23"取走 3 拼进答案,这格也变灰。候选池剩 [1,4]。答案变 "23"。
13. 15k 归 02 ÷ 2 余 0,k 归 0。k=0 是个友好信号:剩下每一位都直接取候选池里最小的那个。继续第 3 位。
14. 16剩 2 个 → 块大小 = 1!剩 1、4 两个,块大小 1!=1。idx = 0÷1 = 0,取剩余候选里下标 0 的数,也就是最小的 1。
15. 17答案 = "231"取走 1 拼进答案,变灰。k 仍是 0。候选池只剩 [4] 一个数了。答案 "231"。
16. 18答案 = "2314"最后一位,候选池只剩 4,直接拿走。紫框指着它——第 4 位是 4。
17. 19四位全定 ✓四位全部定完。按取走顺序拼起来:2、3、1、4 → 答案 "2314"。全程没数过一个排列,直接用阶乘除法跳到位。
18. 20k−1 = 2换 n=3, k=3 再走一遍(灰掉 4,只用前 3 个)。k 减 1 得 2。看公式是不是照样把答案算出来。
19. 21下标 1 → 2剩 3 个数、块大小 2!=2。2÷2 = 1,紫框指向下标 1 的 2。第 1 位定为 2。
20. 22答案 = "2",k 归 0取走 2 拼进答案、变灰。k 更新 2%2 = 0,接下来每位取剩余最小的。
21. 23答案 = "21"k 是 0,第 2 位直接取剩余候选里最小的 1。答案变 "21"。
22. 24答案 = "213"最后只剩 3,拿走。答案 "213"——和手数 [123,132,213] 第 3 个完全吻合,公式照样灵。
23. 25魔法在于:排列天然按首位分块、块大小是阶乘。除法跳到块、取余进块内,把「数到第 k 个」变成 n 次算术。
24. 29k=9 直接除 → 取错首位若不先把 k 减 1,首位 idx 这次碰巧也得 1,但取余会得 3(应为 2)→ 后面每一位都偏,排出错误答案。k 减 1 是地基。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def getPermutation(self, n, k):
        import math
        nums = list(range(1, n + 1))   # 候选池
        k -= 1                         # 转成从 0 数起
        res = []
        for i in range(n, 0, -1):
            f = math.factorial(i - 1)  # 块大小
            idx = k // f               # 取第几个
            res.append(str(nums[idx]))
            nums.pop(idx)              # 取走
            k %= f                     # 缩小到块内
        return "".join(res)

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> nums;
        int f = 1;
        for (int i = 1; i <= n; i++) { nums.push_back(i); f *= i; }
        k -= 1;                         // 从 0 数起
        string res;
        for (int i = n; i >= 1; i--) {
            f /= i;                     // 块大小 = (i-1)!
            int idx = k / f;            // 取第几个
            res += to_string(nums[idx]);
            nums.erase(nums.begin() + idx);
            k %= f;                     // 缩小到块内
        }
        return res;
    }
};

class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> nums = new ArrayList<>();
        int f = 1;
        for (int i = 1; i <= n; i++) { nums.add(i); f *= i; }
        k -= 1;                         // 从 0 数起
        StringBuilder res = new StringBuilder();
        for (int i = n; i >= 1; i--) {
            f /= i;                     // 块大小 = (i-1)!
            int idx = k / f;            // 取第几个
            res.append(nums.get(idx));
            nums.remove(idx);
            k %= f;                     // 缩小到块内
        }
        return res.toString();
    }
}

复杂度

面试官可能追问