LeetCode题练习与总结：排列序列--60

一、题目描述

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

二、解题思路

1. 创建一个列表 nums，其中包含从 1 到 n 的所有数字。
2. 计算 (n-1)! 的值，因为这是每个数字开头的排列数量。
3. 从 k-1（因为我们的列表是从 0 开始的）中减去 (n-1)! 的整数倍，得到剩余的值 offset。
4. offset / (n-2)! 将给出当前位的数字在 nums 中的索引。
5. 使用该索引从 nums 中获取数字，并将其添加到结果字符串中。
6. 从 nums 中移除该数字。
7. 重复步骤 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时，直接取列表中的最后一个元素，这是对边界条件的处理。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。