leetcode: Permutation Sequence

问题描述：

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):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

 

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

 

原问题链接：https://leetcode.com/problems/permutation-sequence/

 

问题分析

思路一：

　这个问题比较容易想到的一种思路就是按照前面一篇讨论排列生成的文章里所说的那样，根据所要生成的的排列顺序来依次生成排列。这种方式有一个问题，就是每次如果要生成我们给定的第几个排列时，它只能从第一个排列顺序的往后生成。相对来说，这种方式的代码有点长，但是有一个固定的规律和格式。在具体的实现里，只需要根据前面生成排列的方法里加一个循环，一直到给定的第k个。

　　因为相对来说该方法的执行效率并不理想，这里就不详细实现了。

 

思路二：

　　除了前面蛮算的方法，这里还有一个可以利用的规律。当然，需要我们稍微仔细一点的观察。假定以n = 4为例。它对应数字１, 2, 3, 4所形成的排列。按照我们的基本理解，一个数字n的所有排列有n!个。那么对应数字４，它所形成的排列有4! = 24个。

　　如果我们把它们按照从小到大的顺序排列起来，同时，所有第一个数字相同的数字排一列，则它所有的排列形成如下的样子：

 

    1234    2134    3124    4123
    1243    2143    3142    4132
    1324    2314    3214    4213
    1342    2341    3241    4231
    1423    2413    3412    4312
    1432    2431    3421    4321

　　从阶乘的基本规律我们可以看到对于数字n来说，从1到n的每个数字开头的排列有(n - 1)!个。就像前面这样，以1, 2, 3, 4分别开头的排列它们每个都是有6个。因此对于我们的数字k来说，它对(n - 1)!相除得到的值就是当前所在的列，这个列索引就是我们所要确定的第一个元素。而它对(n - 1)!取余数，得到的数字就是当前剩余数组的index，因此也就可以得到对应的元素。在具体的实现里，我们需要用一个数组来保存数字1到n，每次找到对应索引的时候，从数组里把这个元素取出来加入到结果数组中，并将它从原来的数组里删除。

　　以前面的数字４为例，假设我们要取第8个排列所在的位置，因为索引从0开始，所以相当于求索引位置为7的那个排列。按照前面的推导过程，首先我们要求它首个位置的元素，因为3! = 6，　7 / 6 = 1。所以我们要从索引１里面找，也就是排列数组里的数字２。这个时候我们去掉数字２，排列数组里的元素是[1, 3, 4]，我们目前的结果数组里的数字是２。这个时候按照同样的方式来推导，我们确定了是在第二列。我们要找的下一个元素的index是7 % 6 = 1。而这时候要求的下一级的阶乘则是2! = 2。1 / 2 = 0，所以取数字１。目标数组现在是[2, 1]，排列数组里剩余元素为[3, 4]。这个时候再求下一个的元素。因为这一级的阶乘是1! = 1，而当前1 / 1 = 1，所以我们需要找到索引位置是1。所以要取的下一个元素就是4。此时结果数组里包含有数字[2, 1, 3]。而此时1 % 1 = 0，下一个要计算的当前值就是0。不过对于最后这个元素可以不用计算了，直接取出来放到最后的结果数组里就是我们期望的结果。

　　按照上述的讨论，我们可以得到如下的代码：

 

public class Solution {
    public String getPermutation(int n, int k) {
        int fact = 1;
        for (int i = 2; i < n; i++) {
            fact *= i;
        }
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            nums.add(i);
        }
        int rank = k - 1;
        StringBuilder ans = new StringBuilder();
        for (int i = n - 1; i > 0; --i) {
            int index = rank / fact;
            ans.append(nums.remove(index));
            rank %= fact;
            fact /= i;
        }
        ans.append(nums.remove(0));
        return ans.toString();
    }
}

 

参考材料

https://leetcode.com/discuss/85678/share-my-java-code

http://blog.csdn.net/linhuanmars/article/details/22028697