Leetcode 60: Permutation Sequence

发表于 更新于 分类于 阅读次数：

Problem

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.

Solution

解题思路

寻找排列顺序规律，可以得出如下排序规律：

  1. 整个排序可以划分成n个小排序。以1为首，[2, 3]的子序列排序。以2为首，[1, 3]的子序列排序， 以3为首，[1, 2]的子序列排序。

  2. 再次划分，则可以将以1为首的排序中，分成以2为第二位， [3]的全排列，和以3为第二位，[2]的全排列。

  3. 逐次划分，分别能将长度为n的序列分解成n个(n-1)全排列，n*(n-1)个(n-2)的全排列，…n!个(1)的全排列。

程序设计

在知晓序列排序规律后，可以着手考虑将第k个元素找到。搜索定位的思想类似于一棵树的节点查找，这棵树的结构已经找到：第一层儿子有n个，第二层的孙子节点共有n*(n-1)个，且每个儿子拥有(n-1)个儿子，以此类推。

而第k个元素对应的元素如何计算出呢？根据这棵树的特点，我们可以做出如下设计，使得从树根到第k个节点的路径就是我们所需要的元素。

  1. 假设树根节点是个空节点，其的n个儿子分别为1, 2, 3, 4, 5,…, n。

  2. 第一层的节点1拥有(n-1)个儿子，分别为2, 3, 4, 5,…n。

  3. 第二层节点2拥有(n-2)个儿子，分别为3, 4, 5,…n。 而第二层节点3拥有N(n-2)个儿子，分别为2, 4, 5,…n。尤其需要注意，儿子的顺序是除开父亲节点后的顺序结构。

时间复杂度树的高度，为O(n)。

实现技巧

从1到n的全排列值计算具有较高的代码重复性， 可以用如下算法进行缓存，从而减少反复计算产生的时间消耗。

1
2
3
4
5
6
7
8
9
// dynamic length int array declaration!!!
int[] factorial = new int[n+1];
// create an array of factorial lookup
    int sum = 1;
    factorial[0] = 1;
    for(int i=1; i<=n; i++){
        sum *= i;
        factorial[i] = sum;
    }

对于元素生成，可以运用List类型的灵活性而避免在元素中挪动数字造成的时间开销。即使int array也可以作为一种高效的数据结构。

在程序实现中，递归算法会产生较高的空间开销，在for循环可以完成计算的情况下，优先采用后者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
List<Integer> numbers = new ArrayList<>();
StringBuilder sb = new StringBuilder();

// create a list of numbers to get indices
for(int i=1; i<=n; i++){
    numbers.add(i);
}
// numbers = {1, 2, 3, 4}

k--;

for(int i = 1; i <= n; i++){
        int index = k/factorial[n-i];
        sb.append(String.valueOf(numbers.get(index)));
        numbers.remove(index);
        k-=index*factorial[n-i];
    }
    
    return String.valueOf(sb);