LeetCode/60. 第k个排列

60. 第k个排列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

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

给定 n 和 k，返回第 k 个排列。

说明：

• 给定 n 的范围是 [1, 9]。
• 给定 k 的范围是[1, n!]。

示例1：

输入: n = 3, k = 3
输出: "213"

示例2:

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题一看到排列，我们就想到了回溯。如果单纯的生成所有可能取值，再从中获取目标字符串肯定会超时。通过观察，我们可以发现一定的规律，即数字的全排列是成组的。

举个例子，比如我们的n = 4, k = 9，我们有如下的排列：
------------以"1"开头------------
		[1, 2, 3, 4]  index = 0
		[1, 2, 4, 3]  index = 1
		[1, 3, 2, 4]  index = 2
		[1, 3, 4, 2]  index = 3
		[1, 4, 2, 3]  index = 4
		[1, 4, 3, 2]  index = 5
------------以"2"开头------------
		[2, 1, 3, 4]  index = 6
		[2, 1, 4, 3]  index = 7
		[2, 3, 1, 4]  index = 8		这是我们要找的目标值
		[2, 3, 4, 1]  index = 9
		[2, 4, 1, 3]  index = 10
		[2, 4, 3, 1]  index = 11
------------以"3"开头------------
		此处省略。。。。。。。

有了如上的规律，那么我们就可以缩减问题的规模，通过n和k可以算出目标字符串是以哪个数字开头的，然后通过剩下的数字进行排列，再定位我们要找的是该组中的第几个，就可以得到最终的结果。比如说，我们现在的n = 4, k = 9，我们可以计算出每组有(n-1)!=3!=6个排列，然后我们给positon + gap和k进行比较，同时初始化一个变量count用来算出第一个数字是多少，如果positon + gap小于k，说明我们要找的目标字符串肯定不在该组中，如果positon + gap大于k，则该组中有我们的目标字符串。我们通过position = k - (position - gap) - 1来定位目标字符串在该组的位置，通过count--来定位目标字符串在哪个组中。最后，我们用backtrack来生成剩下数字的排列，进行拼接就可以获取到目标字符串。

具体代码如下：

class Solution {
    //存放结果数组
    List<String> res = new LinkedList<>();
    //存放路径
    StringBuilder track;
    //gap为每组间隔，position为结果在该组的位置，count为列表第一个数字的值
    int n, k, gap = 1, position = 0, count = 1;

    public String getPermutation(int n, int k) {
        this.n = n;
        this.k = k;
        //标记当前值是否被使用
        boolean[] used = new boolean[n - 1];
        //计算间隔
        for (int i = n - 1; i > 0; i--) {
            gap *= i;
        }
        //如果position位置大于k时，说明目标列表在当前组中
        while (position < k) {
            position += gap;
            //用来计算第一个数字为几
            count++;
        }
        //寻找目标最终位置
        position = k - (position - gap) - 1;
        count--;
        //组装除结果列表第一个元素外的列表
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i + 1 == count) {
                continue;
            }
            list.add(i + 1);
        }
        //将ArrayList转换为int数组
        int[] nums = list.stream().mapToInt(m -> m).toArray();
        //记录路径
        this.track = new StringBuilder();
        //将列表开头元素加入
        track.append(count);
        backtrack(nums, track, used);
        //获取目标字符串
        return res.get(position);
    }

    void backtrack(int[] nums, StringBuilder track, boolean[] used) {
        //触发结束条件
        //如果track.length() == n，说明生成了一个字符串结果
        if (track.length() == n) {
            res.add(track.toString());
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            //排除不合法的选择
            if (used[i]) {
                continue;
            }
            //将track中未出现的元素加入
            used[i] = true;
            track.append(nums[i]);
            backtrack(nums, track, used);
            //剔除最后一个元素，尝试下一个不同的元素
            used[i] = false;
            track.deleteCharAt(track.length() - 1);
        }
    }
}

当然了，还有一种数学归纳的方法，可以直接判断出目标字符串。所用到的原理和我们上述的比较positon + gap和k的大小，来判断当前位置该填写哪个数字。我们还是以上述的n = 4, k = 9举例，计算出每组有(n-1)!=3!=6个排列，可以定位到第一个位置的数字为2，利用(n-2)!=2!=2和k = k - m * (n - 1)!= 3 ，这里的m是指经过多少个gap定位到目标字符串。接着我们继续重复上面的过程继续往下搜索，由于2 < 3，所以我们可以确定第二位数组为3，利用(n-3)!=1!=1和k = k - m * (n - 2)!= 1，最终可以定位到2314，即我们需要找的目标字符串。

上述两种方法，都对排列的顺序有要求，如果顺序打乱，就不能得到想要的结果。

具体代码请参考官网题解