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

"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.

链接： http://leetcode.com/problems/permutation-sequence/

题解：

数学题，找到第k个permutation sequence。 (题外话 : 现在经常体会到数学学得不够好会有多吃力，但也不必要为了钻牛角尖去做个数学家，要足够好，够用就可以了。但怎样算足够好，怎样算够用，很难界定啊。)

n!可以被分为n组，每组有(n - 1)!个数字。假设k在1 ~ n!的范围内，则凭借k / (n - 1)! 我们可以从找到k中有多少组(n - 1)!，而 k %= (n - 1)!则可以把k映射到 1 ~ (n - 1)!的范围内，我们可以继续使用k / (n - 2)!来找到第二大的数字，以此类推。需要思考的地方是使用一个有效的数据结构，来获得当前的最大数字，以及所剩下最小的数字。我觉得可以使用min heap。这里因为n为1 ~ 9，为简便使用了linkedlist。

还有一个很巧妙的地方是 k--，这样k / (n - 1)!就对应着从0 ~ （n - 1）这n个group，这个结果也是我们linkedlist中取出元素的index。接下来进行 k % = (n - 1)!后， k又继续对应 0 ~ (n - 2)这个 n - 1个group。非常好用。

Time Complexity - O(n)， Space Complexity - O(n)。

public class Solution {
    public String getPermutation(int n, int k) {
        if(n <= 0)
            return "";
        List<Integer> list = new LinkedList<Integer>();
        int factorial = 1;
        
        for(int i = 1; i <= n; i++) {
            list.add(i);
            factorial *= i;
        }
        
        k--;                                            // crucial step, put k into range 0 - (n! - 1)
        StringBuilder sb = new StringBuilder();
        
        while(n > 0) {    // n digits
            factorial /= n;     //get (n - 1)!;
            sb.append(list.remove(k / factorial));       //  k / factorial = most important digits
            k %= factorial;                              //  k % factorial = reflect k to range 0 - ((n - 1)! - 1)
            n--;
        }
        
        return sb.toString();
    }
}

二刷：

二刷的作用，就是清理一刷糊弄过去的题目。这道题目也是卡。主要还是参考了discuss里面Adeath以及melvin.ming.gong的解答。以下的解释很烂，三刷希望总结得好一点。

思路主要是，我们有1 ~ n个字母可以来做全排列，那么假设k是存在于 1到 n！中的一个数字，这个数字就会对应我们的一个全排列字母组合，也就是kth permutation sequence。

下面我们来分析一下全排列每个数字的构成:

假如k = n!，那么结果肯定是9876543421，最大的全排列。最高位的确定是 (k- 1) / (9 - 1)!，就是最高位的数字，是由这个数字的排位k - 1 除以低一位的全排列可能性 (n - 1)!来确定的。
我们先从找到最大的全排列 factorial = n!，
为什么要k - 1。假设我们有一个linkedlist，这个list包含所有数字的集合 - 1, 2, 3, 4, 5, 6, 7, 8, 9。因为链表的开头是从0 开始，我们每次从链表中移除的话，要shift一位。这样 k % (n - 1)!就可以被映射到到 0 到 (n - 1)！这块bucket里。否则我们还要判断 k % (n - 1)是否为0，写一些额外的code
当我们求出最高位的数字 n1之后，那么我们接下来要做的就是，在剩下的数字里，我们更新 factorial /= n，然后找到在linkedlist里面位置是 k / factorial的数字，再将其移除就可以了。
最好加上一些判断，比如 k <= 0的情况，或者k > n！的情况。

Java:

Time Complexity - O(n²)， Space Complexity - O(n)。 O(n²)因为我们用到了linekedlist的remove。假如 n属于 1 ~ 9的话其实可以认为是O(1)， O(1)。

public class Solution {
    public String getPermutation(int n, int k) {
        if (k <= 0) {
            return "";
        }
        List<Integer> nums = new LinkedList<>();
        int factorials = 1;
        for (int i = 1; i <= n; i++) {
            nums.add(i);
            factorials *= i;
        }
        while (k > factorials) {
            if (k % factorials == 0) {
                k = factorials;
            } else {
                k %= factorials;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (k--; n > 0; n--) {
            factorials /= n;
            sb.append(nums.remove(k / factorials));
            k %= factorials;
        }
        return sb.toString();
    }
}

三刷:

遇到这题还是会卡一点。应该是因为以前思路不够清晰吧。

我们主要是使用以下几个步骤:

先求得[1, n]的factorial，同时创建一个linkedlist，node分别为[1, n]
k--，将k从 1-based转换为0-based，方便以后我们的模操作。
这里可以加一步判断，假如k >= n那么我们返回一个特定的字符串。
在n > 0的时候
1. 我们先把factorial减少到(n - 1)!
2. 然后我们计算k 中有多少个(n - 1)!，把这个数字作为linkedlist中的index找到相应的节点，删除这个节点并且将其值加到sb中
3. 使用 k % factorial将 k映射到 (n - 1)！的范围内
4. n--，继续下一次操作。
返回结果sb.toString();

Java:

Time Complexity - O(n)， Space Complexity - O(n)。其实因为n只在1 ~ 9中，所以我们可以假定时空间复杂度都是O(1)

public class Solution {
    public String getPermutation(int n, int k) {
        if (k <= 0 || n <= 0) return "";
        List<Integer> nums = new LinkedList<>();
        int factorial = 1;
        for (int i = 1; i <= n; i++) {
            factorial *= i;
            nums.add(i);
        }
        StringBuilder sb = new StringBuilder();
        k--;
        while (n > 0) {
            factorial /= n;
            sb.append(nums.remove(k / factorial));
            k %= factorial;
            n--;
        }
        return sb.toString();
    }
}

Reference：

https://leetcode.com/discuss/16064/an-iterative-solution-for-reference

https://en.wikipedia.org/wiki/Lehmer_code

https://en.wikipedia.org/wiki/Permutation

https://leetcode.com/discuss/42700/explain-like-im-five-java-solution-in-o-n