Description
The set [1, 2, 3, ..., n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123""132""213""231""312""321"
Given n and k, return the kth permutation sequence.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
Example 3:
Input: n = 3, k = 1
Output: "123"
Constraints:
Solutions
Solution 1: Enumeration
We know that the set [1,2,..n] has a total of n! permutations. If we determine the first digit, the number of permutations that the remaining digits can form is (n-1)!.
Therefore, we enumerate each digit i. If k is greater than the number of permutations after the current position is determined, then we can directly subtract this number; otherwise, it means that we have found the number at the current position.
For each digit i, where 0 ≤ i < n, the number of permutations that the remaining digits can form is (n-i-1)!, which we denote as fact. The numbers used in the process are recorded in vis.
The time complexity is O(n^2), and the space complexity is O(n).
PythonJavaC++GoRustC#TypeScript
class Solution:
def getPermutation(self, n: int, k: int) -> str:
ans = []
vis = [False] * (n + 1)
for i in range(n):
fact = 1
for j in range(1, n - i):
fact *= j
for j in range(1, n + 1):
if not vis[j]:
if k > fact:
k -= fact
else:
ans.append(str(j))
vis[j] = True
break
return ''.join(ans)(code-box)
class Solution {
public String getPermutation(int n, int k) {
StringBuilder ans = new StringBuilder();
boolean[] vis = new boolean[n + 1];
for (int i = 0; i < n; ++i) {
int fact = 1;
for (int j = 1; j < n - i; ++j) {
fact *= j;
}
for (int j = 1; j <= n; ++j) {
if (!vis[j]) {
if (k > fact) {
k -= fact;
} else {
ans.append(j);
vis[j] = true;
break;
}
}
}
}
return ans.toString();
}
}(code-box)
class Solution {
public:
string getPermutation(int n, int k) {
string ans;
bitset<10> vis;
for (int i = 0; i < n; ++i) {
int fact = 1;
for (int j = 1; j < n - i; ++j) fact *= j;
for (int j = 1; j <= n; ++j) {
if (vis[j]) continue;
if (k > fact)
k -= fact;
else {
ans += to_string(j);
vis[j] = 1;
break;
}
}
}
return ans;
}
};(code-box)
func getPermutation(n int, k int) string {
ans := make([]byte, n)
vis := make([]bool, n+1)
for i := 0; i < n; i++ {
fact := 1
for j := 1; j < n-i; j++ {
fact *= j
}
for j := 1; j <= n; j++ {
if !vis[j] {
if k > fact {
k -= fact
} else {
ans[i] = byte('0' + j)
vis[j] = true
break
}
}
}
}
return string(ans)
}(code-box)
impl Solution {
pub fn get_permutation(n: i32, k: i32) -> String {
let mut k = k;
let mut ans = String::new();
let mut fact = vec![1; n as usize];
for i in 1..n as usize {
fact[i] = fact[i - 1] * (i as i32);
}
let mut vis = vec![false; n as usize + 1];
for i in 0..n as usize {
let cnt = fact[(n as usize) - i - 1];
for j in 1..=n {
if vis[j as usize] {
continue;
}
if k > cnt {
k -= cnt;
} else {
ans.push_str(&j.to_string());
vis[j as usize] = true;
break;
}
}
}
ans
}
}(code-box)
public class Solution {
public string GetPermutation(int n, int k) {
var ans = new StringBuilder();
int vis = 0;
for (int i = 0; i < n; ++i) {
int fact = 1;
for (int j = 1; j < n - i; ++j) {
fact *= j;
}
for (int j = 1; j <= n; ++j) {
if (((vis >> j) & 1) == 0) {
if (k > fact) {
k -= fact;
} else {
ans.Append(j);
vis |= 1 << j;
break;
}
}
}
}
return ans.ToString();
}
}(code-box)
function getPermutation(n: number, k: number): string {
let ans = '';
const vis = Array.from({ length: n + 1 }, () => false);
for (let i = 0; i < n; i++) {
let fact = 1;
for (let j = 1; j < n - i; j++) {
fact *= j;
}
for (let j = 1; j <= n; j++) {
if (!vis[j]) {
if (k > fact) {
k -= fact;
} else {
ans += j;
vis[j] = true;
break;
}
}
}
}
return ans;
}(code-box)
