Flashcards
Permutation Sequence
Cards in this deck (1)
- 1The 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) {
List numbers = new ArrayList<>();
int[] factorial = new int[n+1];
factorial[0] = 1;
StringBuilder sb = new StringBuilder();
int sum = 1;
for(int i = 1;i<=n; i++){
sum = sum * i;
factorial[i] = sum;
}
k--;
for(int i = 1;i<=n; i++){
numbers.add(i);
}
for(int i = 1; i<=n; i++){
int index = k/factorial[n-i];
sb.append(String.valueOf(numbers.get(index)));
numbers.remove(index);
k = k - index*factorial[n-i];
}
return String.valueOf(sb);
}
Information
- Description
- Flashcards on Permutation Sequence, created by Suhas S on 08/03/2018.
- Created by
- Suhas S
- Views
- 0
- Tags
- Rating