力扣60. 排列序列

描述

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

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

“123” “132” “213” “231” “312” “321”
给定 n 和 k，返回第 k 个排列。

示例 1：
输入：n = 3, k = 3
输出：“213”

示例 2：
输入：n = 4, k = 9
输出：“2314”

示例 3：
输入：n = 3, k = 1
输出：“123”

提示：

1 <= n <= 9
1 <= k <= n!

方法：利用数学规律遍历

思路：
设排列数字个数为n， 求第k个排列，我们可以前往后依次确定第 k 个排列中的每一个位置上的元素。
我们不难发现：以 1 为 a1的排列一共有 (n−1)! 个；
以 2 为 a1的排列一共有 (n−1)! 个⋯。 以 n 为 a 的排列一共有 (n−1)! 个。
因此：
如果 k≤(n−1)!，我们就可以确定排列的首个元素为 1；
如果 (n−1)!<k≤2⋅(n−1)!，我们就可以确定排列的首个元素为 2；
⋯

具体实现及注释：

class Solution {public String getPermutation(int n, int k) {//这个是计算阶乘int[] keyInfomation = new int[n+1];keyInfomation[0] = 1;//标记是否使用boolean[] flags = new boolean[n+1];//记录答案StringBuilder sb = new StringBuilder();for (int i = 1; i <= n; i++) {keyInfomation[i] = i * keyInfomation[i-1];}//这个i代表位数，i=1说明在寻找第一位for (int i = 1; i <= n; i++) {//为什么是k-1呢。首先我们得知道为什么后面会+1，/号是向下取余，比如keyInfomation[n-i]	  //为30， k为35，那么计算结果为1，但其实应该是2，不足应该向上取，所以最后我们需要加//1。但是这样又会出现特殊情况，那就是keyInfomation[n-i]和k相等的时候，如此计算得2，又//与实际需求不符，这时候减1再除就满足题意了int count = (k-1) / keyInfomation[n-i] + 1;//因为通过count我们已经确定了是第几个数放在i这个位置上，我们通过这个循环遍历寻找这个数for (int j = 1; j <=n; j++) {//用过的数字if (flags[j] == true) continue;//先减再判断count--;if (count != 0) {continue;}sb.append(j+"");flags[j] = true;//防止再遍历后面break;}//这个取模是为了便于计算，相当于把前面已经确定的节点忽略掉，专心寻找下一个点。//这儿为什么需要k-1再去模在加一呢，其实如果k ！= keyInfomation[n-i]时候，下面这个式子//和k直接模keyInfomation[n-i]结果是一样的，但是当k等于keyInfomation[n-i]，实际我们需要//的是keyInfomation[n-i]或者k，而不是0。这是一种极限情况。比如我们确定i位上的数字为//5，当k等于keyInfomation[n-i]的时候，代表5确定在i位上的最后一个排列，也是最大的一个//排列，k再多一个，在i这个位置的数字就要取下一个。如果直接模的话，结果为0，就成了5//在i为上的第一个排列，也就是最小的排列，不合题意k = (k-1) % keyInfomation[n-i] + 1;}return sb.toString();}
}