第k个排列

发表于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

LeetCode每日一题，60. Permutation Sequence

先看题目描述

大意就是给 n 个元素的所有排列组合按大小排列出所有情况，返回第 k 个排列

算法和思路

一开始想的是得到所有的排列组合，并按大小排序，然后返回第 k 个。但是看题看着看着出现了思路，想到了一个类似数学的方法，以图中的 Example 2 为例，先用一个列表存储 1 - 4 的 4 个数，即 [1, 2, 3, 4]，给定的 n = 4， k = 9，因为下标应从 0 开始，先把 k - 1 变为 8，然后计算得到 3! = 6，8 / 6 = 1，那么结果的第一个字符为列表里第 1 个元素，即 2，再将 2 删除，列表变为 [1, 3, 4]，再计算 8 % 6 = 2，然后用 2 继续进行上述操作，先得到 2! = 2，然后 2 / 2 = 1，那么继续给结果字符串添加列表里的第 1 个元素，即 3，此时结果字符串变为 “23”，删掉 3，列表变为 [1, 4]，再计算 2 % 2 = 0，然后用 0 继续进行上述操作，1! = 1，0 / 1 = 0，于是给结果字符串添加列表里的第 0 个元素，即 1，此时结果字符串变为 “231”，最后添加列表里剩下的最后一个元素，结果字符串变为 “2314”，然后返回 res ，就按照上面的过程实现代码即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;

class Solution {
    public String getPermutation(int n, int k) {
        if (n == 1) return "1";
        StringBuilder res = new StringBuilder();
        List<String> ss = Arrays.asList("1", "2", "3", "4", "5", "6", "7", "8", "9");
        List stringList = new ArrayList(ss);
        int temp = 1;
        for (int i = n - 1;i >= 2; i--) {
             temp *= i;
        }
        k--;
        for (int i = n - 2; i >= 1; i--) {
            res.append(stringList.get(k / temp));
            stringList.remove(k / temp);
            k %= temp;
            temp /= i + 1;

        }
        res.append(stringList.get(k / temp));
        stringList.remove(k / temp);
        res.append(stringList.get(0));
        return res.toString();
    }
}