Paint Fence

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.

递归

复杂度

O(N) 时间 O(N) 空间

思路

举例：n=3找第5个
递归退出条件：n=1，一个数只能返回一个，就是他自己
对于(n,k)，表示n个数的全排列里找第k个，这n个数放在list里
这n个数构成了n个bucket，每个bucket大小相等，我们可以知道第k个在哪个bucket里。
每个bucket对应一个List里的数字。append到答案里，把这个bucket从list删掉。
最后更新k，让k表示在新桶里的第几小，n减一，继续迭代。

注意

求一个桶多大的时候，要求n!，递归求会超时，用int[]记录下来就好，最多10个数，所以很经济。

代码

public class Solution {
public String getPermutation(int n, int k) {
StringBuilder sb = new StringBuilder();
List list = new ArrayList();
int[] factTable = new int[10];
factTable[1] = 1;
for (int i = 2; i list, StringBuilder sb, int[] factTable) {
if (n == 1) {
sb.append(list.get(0));
return;
}
int fact = factTable[n - 1];
int bucket = (k - 1) / fact;
sb.append(list.get(bucket));
list.remove(bucket);
helper(n - 1, k - fact * bucket, list, sb, factTable);
}
}

关键字：leetcode

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！