LeetCode60(第K个排列)

---

题目：

给出集合[1,2,3,…,n]，其所有元素共有n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定n 和k，返回第k个排列。

说明：
给定 n的范围是 [1, 9]。
给定 k的范围是[1, n!]。

示例1:
输入: n = 3, k = 3
输出: "213"

示例2:
输入: n = 4, k = 9
输出: "2314"

解题思路

1. 首先我们考虑使用全排列的方法，然后找到第k个，举个例子：n = 4, k = 9

首先列出所有的排列
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412 <----> k = 17
3421
4123
4132
4213
4231
4312
4321

2. 全排列的方法太过于复杂，我们可以先找一下规律。

首先，集合为[1,2,3,4]。我们可以发现，每个数字开头的排列个数都是(n-1)!，所以，我们可以通过k值来算出第一位的位置，因为k = 17对应的下标为16，所以，用 16 / 3! = 2，那么第一位应该是集合中的第二个数字3。然后剩下的 16 % 3! = 4。第二层是3个数字，每个数字的排列个数是2!，所以第二位是4 / 2！ = 2，因为3已经被取走，所以这个时候集合中的下标为2的数字是4。然后剩下的 4 % 2! = 0。第三层是2个数字，每个数字的排列个数是1!，所以第三位是 0 / 1! = 0，所以是1。最后是2。 结果是3412。

3. 从2中的逻辑，我们可以得出

k = k - 1

x1 = k / (n - 1)!
k1 = k % (n - 1)!

x2 = k1 / (n - 2)!
k2 = k1 % (n - 2)!
.
.
.
xn-1 = kn-2 / 1!
kn-1 = kn-2 / 1!

xn = kn-1 / 0!
kn = kn-1 % 0!

代码实现

class ThirteenthSolution {
    public String getPermutation(int n, int k) {
        StringBuilder res = new StringBuilder();
        String numStr = "123456789";
        int[] num = new int[n];
        num[0] = 1;
        for (int i = 1; i < n; i++) {
            num[i] = num[i - 1] * i;
        }
        --k;
        for (int i = 1; i <= n; i++) {
            int j = k / num[n - i];
            k %= num[n - i];
            res.append(numStr.charAt(j));
            numStr = numStr.replace(numStr.charAt(j) + "", "");
        }
        return res.toString();

    }
}

public class ByteDanceThirteenth {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            int n = Integer.parseInt(line);
            line = in.readLine();
            int k = Integer.parseInt(line);

            String ret = new ThirteenthSolution().getPermutation(n, k);

            String out = (ret);

            System.out.print(out);
        }
    }
}