力扣第 60 题 “第 k 个排列”

题目描述

给定整数 n 和 k，返回由 1 到 n 组成的排列中第 k 个排列。

• 所有排列按字典序排列。
• 1 ≤ n ≤ 9，1 ≤ k ≤ n!。

---

解题思路

要快速找到第 k 个排列，可以利用数学方法而不是生成所有排列：

1. 知识点：阶乘与字典序

• 对于给定的 n，共有 n! 种排列。
• 每个数字作为排列的起点时，其后续排列数为 (n-1)!。
• 利用这一规律，可以逐步确定排列的每一位。

2. 数学推导

1. 确定第 1 位：

   • k 以 (n-1)! 为单位划分。
   • 第一个数字是 (k-1)/(n-1)! + 1。
   • 更新 k = k % (n-1)!。

2. 重复确定后续数字：

   • 每次缩小范围，使用相同的逻辑继续计算。

3. 数字选择：

   • 使用一个列表存储可选的数字，每次选中一个后移除。

3. 算法步骤

1. 计算阶乘数组，用于快速获取 (n-1)!。
2. 使用数字列表维护当前可以使用的数字。
3. 根据 k 确定每一位数字。

---

C 语言代码实现

以下是完整的 C 语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 主函数：获取第 k 个排列
char* getPermutation(int n, int k) {// 计算阶乘数组int factorial[n];factorial[0] = 1;for (int i = 1; i < n; i++) {factorial[i] = factorial[i - 1] * i;}// 可选数字列表int numbers[n];for (int i = 0; i < n; i++) {numbers[i] = i + 1; // 初始为 [1, 2, ..., n]}// 分配结果字符串char* result = (char*)malloc((n + 1) * sizeof(char));result[n] = '\0'; // 末尾加结束符// 调整为从 0 开始的索引k--;// 构造排列for (int i = 0; i < n; i++) {int index = k / factorial[n - 1 - i]; // 当前数字的索引result[i] = numbers[index] + '0';    // 转为字符// 删除已选数字for (int j = index; j < n - i - 1; j++) {numbers[j] = numbers[j + 1];}k %= factorial[n - 1 - i]; // 更新 k}return result;
}// 测试代码
int main() {int n = 4, k = 9;char* result = getPermutation(n, k);printf("第 %d 个排列是: %s\n", k, result);free(result); // 释放内存return 0;
}

---

代码解析

1. 阶乘数组的计算：

   factorial[0] = 1;
   for (int i = 1; i < n; i++) {factorial[i] = factorial[i - 1] * i;
   }
   

   • 用于快速获取 (n-1)!。

2. 维护可选数字：

   for (int i = 0; i < n; i++) {numbers[i] = i + 1;
   }
   

   • 初始数字列表为 [1, 2, ..., n]。
   • 每选定一个数字后，从列表中移除。

3. 逐步构造排列：

   int index = k / factorial[n - 1 - i]; // 当前数字的索引
   result[i] = numbers[index] + '0';    // 转为字符
   

   • 根据 k 确定当前位的数字索引。
   • 将对应数字从 numbers 中移除，更新 k。

4. 更新索引 k：

   k %= factorial[n - 1 - i];
   

   • 剩余排列数更新为当前范围内的相对位置。

5. 构造字符串：

   • 动态分配内存存储结果，并在末尾添加字符串结束符。

---

复杂度分析

1. 时间复杂度：

   • 阶乘数组计算：O(n)。
   • 每次确定一位数字需移除列表中的一个元素：O(n^2)。
   • 总复杂度为 O(n^2)。

2. 空间复杂度：

   • 需要额外的 O(n) 空间存储数字列表和阶乘数组。

---

测试案例

输入：

n = 4, k = 9

输出：

"2314"

输入：

n = 3, k = 3

输出：

"213"