Using Cantor Expansion, JAVA code


  • 0
    F
    public String getPermutation(int n, int k) {
        int[] factor = new int[n];
        factor[0] = 1;
        for (int i = 1; i < n; i++)
            factor[i] = factor[i - 1] * i;
        k--;
        int[] a = new int[n];
        a[n - 1] = 0;
        for (int i = 0; i < n - 1; i++) {
            a[i] = k / factor[n - 1 - i];
            k %= factor[n - 1 - i];
        }
        StringBuilder result = new StringBuilder();
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++)
            list.add(i + 1);
        for (int i = 0; i < n; i++)
            result.append(list.remove(a[i]));
        return result.toString();
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.