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 (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
public String getPermutation(int n, int k) { // Start typing your Java solution below // DO NOT write main() function ArrayList<Integer> nums = new ArrayList<Integer>(); for(int i=1;i<=n;i++){ nums.add(i); } k--;//k originally starts from 1 int index=0; while(k!=0){ int frac = frac(n-index-1); int targetNumIndex = k/frac+index; int targetNum = nums.remove(targetNumIndex); nums.add(index,targetNum); index++; k=k%frac; } String output = ""; for(Integer num:nums){ output+=num; } return output; } public int frac(int n){ int sum = 1; for(int i=1;i<=n;i++){ sum*=i; } return sum; }