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"
Note: Given n will be between 1 and 9 inclusive.
A:
public class PermutationSequence { public String getPermutation(int n, int k) { ArrayList<Integer> origList = new ArrayList<Integer>(); //add 1 to n into the list, and delete them one by one ArrayList<Integer> resultList = new ArrayList<Integer>(); //add 1 to n into the origList, and delete them one by one for(int i =1;i<=n;i++){ origList.add(i); } int[] numPerm = new int[n+1]; numPerm[0] = 1; for(int i =1;i<=n;i++){ numPerm[i] = numPerm[i-1]*i; } // for each iteration ,find the number that should be for(int i =1;i<=n;i++){ /// find the i_th position int numCounted = 1; int numLeftPermu = numPerm[n-i]; while(numCounted*numLeftPermu < k ){ numCounted ++; } numCounted--; k = k - numCounted*numLeftPermu; int extractedValue = origList.remove(numCounted); resultList.add(extractedValue); } StringBuffer buf = new StringBuffer(); for(int i =0;i<resultList.size();i++){ buf.append(resultList.get(i )+""); } return buf.toString(); } }
------------第二遍,------------感觉还没有第一遍思路清晰---------为什么呢??? ----------
public class Solution { public String getPermutation(int n, int k) { // use list ,so that we can easily delete on item ArrayList<Integer> list = new ArrayList<Integer>(); for (int i = 1; i <= n; i++) list.add(i); int result[] = new int[n]; // calculate how many permutation for this count = index i int count[] = new int[n+1]; count[0] = 1; for (int i = 1; i <= n; i++) count[i] = i * count[i-1]; // couting backward for (int i = 0; i < n; i++) { // for n position of for (int j = 0; j < list.size(); j++) { if ((j + 1) * count[ list.size() -1] >= k) { // we should start from list.get(j) result[i] = list.remove(j); k -= j*count[list.size() ]; break; } } } String tmp = Arrays.toString(result).replace(", ","");; return tmp.substring(1,tmp.length()-1); } }
Mistakes:
1: 最后的 buf.append(resultList.get(i )+""); 开始的时候,由于光考虑 i 转成string的情况去了,因此,直接写的是 buf.append( i +"");
可惜了啊, 否则就是直接pass过了, O(∩_∩)O哈哈~
2: 第二遍的时候,
if ((j + 1) * count[ list.size() -1] >= k) { 这里, 要有等号的,仔细想想,为什么
-----------------------------------------3 rd Pass -----------------------------------------
TMD 就是脑子不清醒,非想要一个循环。 哎,至于吗? 浪费了好几个小时。
结果明白了一点儿。 要计算k_th的permu,由于我们是用了一个数组, nPerm【】 来计算少了一个的数的时候,有多少个变化。 是在求 之前的变化。 因此,我们在计算
前面多少个重复的时候,应该用 k-1 来计算前面的变化数字。
哎,真为你的智商着急阿, Tiger
public class Solution { public String getPermutation(int n, int k) { ArrayList<Integer> al = new ArrayList<Integer>(); StringBuffer buf = new StringBuffer(); int[] nPermu = new int[n+1];// number of permutation before using index i nPermu[0] = 1; for(int i =1;i<=n;i++){ nPermu[i] = i*nPermu[i-1]; al.add(i); } // to get k-th, we need count k-1 before this one while(al.size()>0 ){// determine each digits from the highest int nRepeat = (k-1) / nPermu[al.size()-1]; k -= nRepeat * nPermu[al.size()-1]; buf.append(al.remove(nRepeat)); } return buf.toString(); } }
Learned:
No comments:
Post a Comment