首页 > 代码库 > LeetCode 笔记21 生成第k个排列
LeetCode 笔记21 生成第k个排列
题目是这样的：
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.
就是说，按字典序给出第k个排列。
因为之前做了“生成下一个排列”的题目，就直接拿过来用了。不料超时，于是只能用数学的方法做了。当然这也不是我想出来的，而是搜出来的（逃。。。）
基本的想法是，对于第k个排列，{a1, a2, a3, ..., an}, a1 是多少呢？
因为{a2, a3, ..., an} 一共有 (n-1)!种，a1在num中的index相当于 k / (n-1)!。换句话解释，就是一共有n个block，每个block大小是(n-1)!这么大，现在要求的就是在哪个block。
同理，求a2的时候，a1（在哪个block）已经求出来了，update k = k % (n-1)!, block的大小变成了(n-2)!, 这又是一个子问题了。
代码如下：
1 public String getPermutation(int n, int k) { 2 int[] num = new int[n]; 3 int perNumCount = 1; 4 5 for(int i = 0; i < n; i++) { 6 num[i] = i+1; 7 perNumCount *= i + 1; 8 } 9 k--;10 StringBuilder sb = new StringBuilder();11 for(int i = 0; i < n; i++) {12 perNumCount = perNumCount / (n - i);13 int choosed = k / perNumCount;14 sb.append(String.valueOf(num[choosed]));15 for(int j = choosed; j < n - i - 1; j++) {16 num[j] = num[j+1]; 17 }18 k = k % perNumCount;19 }20 return sb.toString();21 }
LeetCode 笔记21 生成第k个排列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。