一、题目描述
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"
给定 n 和 k，返回第 k 个排列。
示例 1：
输入：n = 3, k = 3 输出："213"
示例 2：
输入：n = 4, k = 9 输出："2314"
示例 3：
输入：n = 3, k = 1 输出："123"
提示：
1 <= n <= 91 <= k <= n!
二、解题思路
- 创建一个列表
nums，其中包含从 1 到 n 的所有数字。 - 计算 (n-1)! 的值，因为这是每个数字开头的排列数量。
- 从 k-1（因为我们的列表是从 0 开始的）中减去 (n-1)! 的整数倍，得到剩余的值
offset。 offset / (n-2)!将给出当前位的数字在nums中的索引。- 使用该索引从
nums中获取数字，并将其添加到结果字符串中。 - 从
nums中移除该数字。 - 重复步骤 2-6，直到找到第 k 个排列。
三、具体代码
import java.util.ArrayList;
import java.util.List;
public class Solution {
public String getPermutation(int n, int k) {
// Step 1: 创建一个列表 nums，其中包含从 1 到 n 的所有数字
List<Integer> nums = new ArrayList<>();
for (int i = 1; i <= n; i++) {
nums.add(i);
}
// 计算 (n-1)!
int fact = 1;
for (int i = 1; i <= n - 1; i++) {
fact *= i;
}
// 从 k-1 中减去 (n-1)! 的整数倍
k--;
StringBuilder result = new StringBuilder();
// 重复步骤 2-6，直到找到第 k 个排列
for (int i = n; i >= 1; i--) {
// 计算 offset
int index = k / fact;
k %= fact;
// Step 4: 使用该索引从 nums 中获取数字，并将其添加到结果字符串中
result.append(nums.get(index));
// Step 6: 从 nums 中移除该数字
nums.remove(index);
// 更新 (n-1)!
if (i > 1) {
fact /= (i - 1);
}
}
return result.toString();
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 初始化列表
nums的时间复杂度是 O(n)，因为需要遍历从 1 到 n 的所有数字。 - 计算 (n-1)! 的时间复杂度是 O(n)，因为需要循环 n-1 次。
- 主循环中，每次迭代都会从列表
nums中移除一个元素，并且更新 (n-1)! 的值。这个循环会执行 n 次，每次操作的时间复杂度是 O(1)，因为列表nums的长度在不断减少，而且更新 (n-1)! 的值是常数时间操作。 - 因此，总的时间复杂度是 O(n) + O(n) + O(n) * O(1) = O(n)。
2. 空间复杂度
- 需要一个列表
nums来存储从 1 到 n 的所有数字，因此空间复杂度是 O(n)。 - 需要一个
StringBuilder来构建结果字符串，其空间复杂度也是 O(n)。 - 其他变量（如
fact和index）使用的空间是常数的，因此可以忽略不计。 - 因此，总的空间复杂度是 O(n) + O(n) = O(n)。
五、总结知识点
1. 数据结构:
ArrayList: 是Java集合框架中的一部分，用于存储动态数组。它允许我们存储和操作可变大小的元素集合。
2. 循环结构:
for循环: 用于初始化列表nums和计算(n-1)!。这是Java中常用的控制流语句，用于重复执行一段代码固定的次数。
3. 算术运算:
- 幂运算和阶乘: 代码中通过循环计算
(n-1)!，这是基础的数学运算在编程中的体现。
4. 字符串操作:
StringBuilder: 用于构建和修改字符串。由于字符串是不可变的，使用StringBuilder可以提高频繁修改字符串时的性能。
5. 算法思想:
- 排列组合: 代码的核心是找到一个给定序列的第k个排列。这涉及到排列组合的数学概念，以及如何通过计算来找到特定的排列。
6. 列表操作:
remove(int index): 用于从列表中移除指定位置的元素。这是对列表进行动态修改的常见操作。
7. 变量和类型:
int: 是Java中的基本数据类型之一，用于表示整数。StringBuilder: 是一个类，用于表示可变的字符序列。
8. 函数和方法:
public String getPermutation(int n, int k): 这是一个公共方法，接受两个整数参数n和k，并返回一个字符串。这是面向对象编程中封装和抽象的体现。
9. 递归和迭代:
- 虽然这段代码没有直接使用递归，但是它使用了迭代的方式来逐步构建最终的排列字符串。
10. 边界条件处理:
- 当
k减去(n-1)!的整数倍后剩余为0时，直接取列表中的最后一个元素，这是对边界条件的处理。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
