当前位置： 面试刷题>> 第k个排列 (经典算法题500道)
### 题目描述
给定一个包含从1到n的所有整数的数组，和一个整数k，返回这个数组中第k个排列。
排列从序列的字典序排列开始定义。例如，给定数组 `[1,2,3]`，其排列为:
```
"123"
"132"
"213"
"231"
"312"
"321"
```
对于n = 3 和 k = 4，则第4个排列为 `"231"`。
### 解题思路
我们可以使用回溯法（或称为深度优先搜索）来解决这个问题，但更高效的方法是使用数学方法来定位第k个排列。基本思路是：
1. 从最高位（即数组的开头）开始，通过计算当前位上可以放置的数字的个数（未使用的数字），来确定当前位的数字。
2. 确定当前位数字后，计算其前面所有小于它的数字的个数，这决定了当前数字是第几个排列的起始部分。
3. 递归地处理剩余的数组和剩余的k值。
### PHP 示例代码
```php
function getPermutation($n, $k) {
$nums = range(1, $n);
$factorial = array_fill(0, $n, 0);
$factorial[0] = 1;
for ($i = 1; $i < $n; $i++) {
$factorial[$i] = $factorial[$i - 1] * $i;
}
$k--; // 转换为从0开始的索引
$result = '';
while ($n > 0) {
$groups = $factorial[$n - 1];
$digit = intdiv($k, $groups) + 1;
$k = $k % $groups;
// 找出当前位的数字，并将其从数组中移除
$result .= array_splice($nums, $digit - 1, 1)[0];
$n--;
}
return strrev($result); // 因为是从高位到低位构建的，所以需要反转字符串
}
// 示例
echo getPermutation(3, 4); // 输出: 231
```
### Python 示例代码
```python
def getPermutation(n, k):
nums = list(range(1, n + 1))
factorial = [1] * n
for i in range(1, n):
factorial[i] = factorial[i - 1] * i
k -= 1
result = []
while n > 0:
groups = factorial[n - 1]
digit = (k // groups) + 1
k %= groups
result.append(str(nums.pop(digit - 1)))
n -= 1
return ''.join(result)
# 示例
print(getPermutation(3, 4)) # 输出: 231
```
### JavaScript 示例代码
```javascript
function getPermutation(n, k) {
const nums = Array.from({ length: n }, (_, i) => i + 1);
const factorial = Array(n).fill(1).map((_, i) => i ? factorial[i - 1] * i : 1);
k--; // 转换为从0开始的索引
let result = '';
while (n > 0) {
const groups = factorial[n - 1];
const digit = Math.floor(k / groups) + 1;
k %= groups;
// 找出当前位的数字，并将其从数组中移除
result += nums.splice(digit - 1, 1)[0];
n--;
}
return result;
}
// 示例
console.log(getPermutation(3, 4)); // 输出: 231
```
码小课网站中有更多相关内容分享给大家学习，欢迎访问码小课网站深入学习更多编程知识和算法技巧。