60. Permutation Sequence
集合 [1, 2, 3, ..., n] 總共有 n! 個唯一的排列。
通過按順序列出並標記所有排列，我們得到 n = 3 的以下序列：
"123" "132" "213" "231" "312" "321"
給定 n 和 k，返回第 k 個排列序列。
範例 1：
輸入：n = 3, k = 3 輸出：213
Python
from typing import List
class Solution:
def getPermutation(self, n: int, k: int) -> str:
# Compute factorials
factorials = [1] * n
for i in range(2, n):
factorials[i] = factorials[i - 1] * i
# Create a list of numbers to get the sequence from
numbers = list(range(1, n + 1))
# Adjust k to be zero-indexed
k -= 1
# Build the k-th permutation
result = []
for i in range(n, 0, -1):
# Determine the index of the current digit
index = k // factorials[i - 1]
result.append(str(numbers[index]))
# Remove the used number
numbers.pop(index)
# Update k
k %= factorials[i - 1]
return ''.join(result)
16.84MB, 41ms
C++
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string getPermutation(int n, int k) {
// Compute factorials
vector<int> factorials(n, 1);
for (int i = 2; i < n; ++i) {
factorials[i] = factorials[i - 1] * i;
}
// Create a list of numbers to get the sequence from
vector<int> numbers;
for (int i = 1; i <= n; ++i) {
numbers.push_back(i);
}
// Adjust k to be zero-indexed
k -= 1;
// Build the k-th permutation
string result;
for (int i = n; i > 0; --i) {
// Determine the index of the current digit
int index = k / factorials[i - 1];
result += to_string(numbers[index]);
// Remove the used number
numbers.erase(numbers.begin() + index);
// Update k
k %= factorials[i - 1];
}
return result;
}
};
7.38MB, 0ms
Javascript
/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var getPermutation = function(n, k) {
// Compute factorials
const factorials = Array(n).fill(1);
for (let i = 2; i < n; i++) {
factorials[i] = factorials[i - 1] * i;
}
// Create a list of numbers to get the sequence from
const numbers = [];
for (let i = 1; i <= n; i++) {
numbers.push(i);
}
// Adjust k to be zero-indexed
k -= 1;
// Build the k-th permutation
let result = '';
for (let i = n; i > 0; i--) {
// Determine the index of the current digit
const index = Math.floor(k / factorials[i - 1]);
result += numbers[index];
// Remove the used number
numbers.splice(index, 1);
// Update k
k %= factorials[i - 1];
}
return result;
};
49.17MB, 57ms
