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):
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.
Solution:O(n)
public class Solution { public String getPermutation(int n, int k) { ArrayList<Integer>list = new ArrayList<> (); for (int i = 1; i <= n; i++) { list.add(i); } k--; int mod = 1; for (int i = 1; i <= n; i++) { mod = mod * i; } String ret = ""; for (int i = 0; i < n; i++) { mod = mod / (n - i); int curIndex = k / mod; k %= mod; ret += list.get(curIndex); list.remove(curIndex); } return ret; } }
Key Concept:Use factorial and determine the first element and so on.
沒有留言:
張貼留言