月度归档： 2022年6月

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

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

输入：n = 3, k = 1
输出："123"

逆康托展开 与 康托展开【Cantor Expansion】
关于本题原型可以参见下康托展开【Cantor Expansion】 ,就是原题了，具体内容不做更多赘述

思路

1. 已知现有数字n，那么按字典序排序组合后我们知道。初步的根据第1位的字符可以分成n段，每段长度为(n-1)!
2. 继而我们这当中的某一段中，我又可以如上分成(n-1)段，因为前面已经用了一位数字了，而这(n-1)段的每段长度为(n-2)!
3. 那么按照题意，我们可以按照从大区间到小区间逐步缩小范围的方法来处理
4. 首先除以(n-1)!，得到第一位的数字，记下余数
5. 用上一步的余数除以(n-2)!，知道了第二位数字，继续记下余数用来处理第三位数字
6. 每次除以(n-?)!得到的结果是确定的未使用的数字的顺序，即在确定这个数字的时候需要跳过前面已经使用过的数字，见方法findNthNum(int nth)
7. 最终还剩下一个数字，就是最后一位了

容易掉的坑，k--，上来记得要减下，被这步坑了好久，减一之后直接除了便于取整取余划分区间

代码

class Solution {

    boolean[] usedNums;

    public String getPermutation(int n, int k) {
        k--;
        usedNums = new boolean[n+1];
        int[] factorial = new int[n];
        factorial[n-1] = 1;
        for (int i = n-2; i >= 0; i--) {
            factorial[i] = factorial[i+1] * (n-i);
        }
        char[] ans = new char[n];
        int idx = 0;
        while (++idx < n){
            int i = k / factorial[idx];
            k %= factorial[idx];
            int num = findNthNum(i+1);
            ans[idx-1] = (char)('0'+ num);
        }
        ans[idx-1] = (char)('0'+ findNthNum(1));
        return new String(ans);
    }

    int findNthNum(int nth){
        for (int i = 1; i < usedNums.length; i++) {
            if(!usedNums[i]){
                nth--;
                if (nth==0){
                    usedNums[i] = true;
                    return i;
                }
            }
        }
        return -1;
    }
}

以上其实是逆康托展开的过程，根据第k的数值，确定这个数值是什么

根据定义，与这一过程相对的是康托展开的过程，根据数值确定这个数值的排序

那么相应思路为

1. 从头开始确定当前数字在未使用数字中的排序i（从0下标开始或者你认为从正数1开始排序i'那么前面有i'-1组）,那么前面有i * (n-1)!个
2. 第二位同样假设第二位数字在未使用数字中的排序i_1(下标)，第二位则对应为i_1 * (n-2)!
3. 后面依次叠加
4. 最终得到的结果即为对应的排序