LeetCode [60] Permutation Sequence

 60. Permutation Sequence

Hard

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.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: int factorial(int n){ if(n==0) return 1; return n*factorial(n-1); } string getPermutation(int n, int k) { string s; vector<char> nums; for(int i=1; i<=n; ++i) nums.push_back('0'+i); k--;//0-based while(s.size()<n){ int cnt_group = factorial(n-s.size()-1); int id_group = k/cnt_group; s += nums[id_group]; nums.erase(nums.begin()+id_group); k -= cnt_group*id_group; } return s; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

public class Solution { public String getPermutation(int n, int k) { int pos = 0; List<Integer> numbers = new ArrayList<>(); int[] factorial = new int[n+1]; StringBuilder sb = new StringBuilder(); // create an array of factorial lookup int sum = 1; factorial[0] = 1; for(int i=1; i<=n; i++){ sum *= i; factorial[i] = sum; } // factorial[] = {1, 1, 2, 6, 24, ... n!} // create a list of numbers to get indices for(int i=1; i<=n; i++){ numbers.add(i); } // numbers = {1, 2, 3, 4} k--; for(int i = 1; i <= n; i++){ int index = k/factorial[n-i]; sb.append(String.valueOf(numbers.get(index))); numbers.remove(index); k-=index*factorial[n-i]; } return String.valueOf(sb); } }