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:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "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 <= 9
  • 1 <= 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)$.

  • 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:
            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)
    
    ##########
    
    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)
    
    
  • 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
        }
    }
    
    

All Problems

All Solutions