LeetCode每日一题：permutation sequenc

问题描述

The set[1,2,3,…,n]contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the k_th permutation sequence.
Note: Given n will be between 1 and 9 inclusive.

问题分析

这题直接穷举会超时，肯定不能。其中涉及到一个数学问题：

在n!个排列中，第一位的元素总是(n-1)!一组出现的，也就说如果p = k / (n-1)!，那么排列的最开始一个元素一定是nums[p]。

代码实现

public String getPermutation(int n, int k) {
        k--;
        int[] num = new int[n];
        int cnt = 1;
        for (int i = 0; i < n; i++) {
            num[i] = i + 1;
            cnt = cnt * (i + 1);
        }
        char[] result = new char[n];
        for (int i = 0; i < n; i++) {
            cnt = cnt / (n - i);
            int p = k / cnt;
            result[i] = (char) ('0' + num[p]);
            for (int j = p; j < n - 1 - i; j++) {
                num[j] = num[j + 1];
            }
            k = k % cnt;
        }
        return new String(result);
    }