Welcome to Subscribe On Youtube
60. Permutation Sequence
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:
1 <= n <= 91 <= k <= n!
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 \leq 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)$.
Why k -= 1 is Needed ?
Adjust k:
- The statement
k -= 1adjusts the offsetkto zero-based indexing. This is necessary because the problem statement assumes 1-based indexing (i.e., the 1st permutation, not the 0th). In zero-based indexing, it simplifies calculations, especially when determining which element ofnumsto append to the result in each iteration.
The adjustment k -= 1 is crucial for aligning the k-th permutation request with the way the algorithm segments permutation groups. Since the permutations are considered in a zero-based manner inside the algorithm (where the first permutation in lexicographic order is at index 0, the second at index 1, and so on), decrementing k by 1 allows the division and modulus operations to correctly calculate indices in nums and the remaining k for subsequent digits. Without this adjustment, you would be off by one, trying to access the “next” group of permutations when you should be looking at the “current” one, leading to incorrect results.
Let’s say n = 3 and k = 4. The permutations in lexicographic order are:
- 123
- 132
- 213
- 231 ← We want this one
- 312
- 321
Adjusting k to zero-based, k = 3, helps us directly index into these permutations as if they were an array starting from index 0, simplifying the logic to find the 4th permutation (which is at index 3 in zero-based).
-
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(); } } -
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; } }; -
class Solution: def getPermutation(self, n: int, k: int) -> str: nums = list(range(1, n + 1)) factorial = [1] * (n + 1) for i in range(1, n + 1): factorial[i] = factorial[i - 1] * i result = [] k -= 1 for i in range(n, 0, -1): digit = k // factorial[i - 1] result.append(str(nums[digit])) nums.pop(digit) k %= factorial[i - 1] return ''.join(result) ########## 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) -
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) } -
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(); } } -
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 } }