首页 > 代码库 > leetcode 60 Permutation Sequence ----- java
leetcode 60 Permutation Sequence ----- java
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.
这道题就是给出一个数字n和一个数字k，然后在由1-n的所有数字组成的排列组合中，输出第k个。规则如上(先改变后面的数字，就是比如四个数字，第一个是1234，第二个是1243)
然后这道题想清楚思路也就比较简单了。
总共有n个数字，那么以每个数字开头都有(n-1)!种，也就是说如果 1<=k<=(n-1)! 那么这个组合就会以1开头。
确定了第一个数字之后，那么就以同样的方法确定之后的数字，在第一个数字确定的基础上，以某个数字都有(n-2)!种 ，所以就可以推断出：
求第k个字符串的时候，从前到后依次确定数字;count指的就是当前数字中，以某个数字开头的组合的种类个数。
public class Solution { public String getPermutation(int n, int k) { int[] flag = new int[n]; String result ; char[] ans = new char[n]; int count = 1; for( int i = 2;i<n;i++) count*=i; for( int i = 0;i<n;i++){ if ( k == 1){ for( int j = 0;j<n;j++){ if( flag[j] == 0){ ans[i] = (char) (j+49); i++; flag[j] = 1; } } return new String(ans); } int num = (k-1)/count; k = k - num*count; count = count/(n-1-i); for( int j = 0;j<n;j++){ if( flag[j] == 0){ if( num == 0){ ans[i] = (char) (j+49); flag[j] = 1; break; }else num--; } } } return new String(ans); }}
这道题是难得的一次提交就到达最快的时候。
leetcode 60 Permutation Sequence ----- java
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。