Sponsored
Sponsored
This approach leverages the factorial number system, where the number of permutations starting with a particular digit can be determined by the factorial of (n-1). We adjust k for zero-based indexing and deduct permutations as we determine each digit sequentially.
Time Complexity: O(n^2) due to potential shifts in the numbers array.
Space Complexity: O(n) for storing factorials and numbers.
1using System;
2using System.Collections.Generic;
3
4class Program {
5 public static string GetPermutation(int n, int k) {
6 List<int> numbers = new List<int>();
7 int[] factorial = new int[n];
8 factorial[0] = 1;
9 for (int i = 1; i < n; i++)
10 factorial[i] = factorial[i - 1] * i;
11 for (int i = 1; i <= n; i++)
12 numbers.Add(i);
13
14 k--;
15 string result = "";
16 for (int i = n; i > 0; i--) {
17 int index = k / factorial[i - 1];
18 result += numbers[index].ToString();
19 numbers.RemoveAt(index);
20 k %= factorial[i - 1];
21 }
22 return result;
23 }
24
25 static void Main() {
26 int n = 3, k = 3;
27 Console.WriteLine(GetPermutation(n, k));
28 }
29}This C# solution relies on List to dynamically retrieve and track digits as the permutation string is built. Each digit is determined by the factorial arrangements of remaining digits.
This approach generates permutations using a traditional backtracking method, with the goal of finding the k-th permutation without necessarily generating all permutations explicitly.
Time Complexity: O(n!) for generating permutations.
Space Complexity: O(n) due to recursion and string storage.
1#
This C solution uses a recursive backtracking approach to generate permutations, counting them until reaching the desired k-th permutation, which is stored for output.