Guest User

Untitled

a guest
Aug 29th, 2021
93
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.  
  3.   int[] factorials;
  4.  
  5.   public String getPermutation(int n, int k) {
  6.     ArrayList<Integer> nums = new ArrayList();
  7.     nums.add(1);
  8.      
  9.     factorials = new int[n];
  10.     factorials[0] = 1;
  11.    
  12.     // calculate all factorials from 1 to n
  13.     for (int i = 1; i < n; i ++) {
  14.       factorials[i] = factorials[i - 1] * i;
  15.      
  16.       nums.add(i + 1);
  17.     }
  18.    
  19.     StringBuilder sb = new StringBuilder();
  20.    
  21.     helper(nums, k, sb);
  22.    
  23.     return sb.toString();
  24.   }
  25.  
  26.   private void helper(ArrayList<Integer> nums, int k, StringBuilder sb) {
  27.     // base case
  28.     if (nums.size() <= 0) {
  29.       return;
  30.     }
  31.    
  32.     // get number of permutation
  33.     int count = factorials[nums.size() - 1];
  34.        
  35.     // skip count blocks for selecting the index
  36.     int selected = (k - 1) / count;
  37.        
  38.     sb.append(nums.get(selected));
  39.    
  40.     nums.remove(selected);
  41.    
  42.     // skip some blocks
  43.     k = k - (selected * count);
  44.    
  45.     helper(nums, k, sb);
  46.   }
  47. }
RAW Paste Data