LeetCode 排列序列题解
题目描述
给定 n 和 k，返回第 k 个排列。
示例：
输入：n = 3, k = 3输出："213"
解题思路
方法：数学
思路：
- 使用数学公式计算第 k 个排列。
- 首先计算每个位置的初始阶乘值。
- 然后逐步确定每个位置的数字。
复杂度分析：
- 时间复杂度：O(n^2)。
- 空间复杂度：O(n)。
代码实现
def get_permutation(n, k):
factorial = [1] * (n + 1)
for i in range(1, n + 1):
factorial[i] = factorial[i – 1] * i
numbers = [str(i) for i in range(1, n + 1)]
k -= 1
result = []
for i in range(n, 0, -1):
index = k // factorial[i – 1]
result.append(numbers.pop(index))
k %= factorial[i – 1]
return ''.join(result)
# 测试
def test_get_permutation():
n, k = 3, 3
print(get_permutation(n, k)) # 输出："213"
if __name__ == "__main__":
test_get_permutation()
总结
排列序列是数学的典型应用，通过计算阶乘值来确定每个位置的数字。
