描述

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

按大小順序列出所有排列情況，并一一標(biāo)記，當(dāng) 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!

方法：利用數(shù)學(xué)規(guī)律遍歷

思路：
設(shè)排列數(shù)字個數(shù)為n， 求第k個排列，我們可以前往后依次確定第 k 個排列中的每一個位置上的元素。
我們不難發(fā)現(xiàn)：以 1 為 a1的排列一共有 (n?1)! 個；
以 2 為 a1的排列一共有 (n?1)! 個?。 以 n 為 a 的排列一共有 (n?1)! 個。
因此：
如果 k≤(n?1)!，我們就可以確定排列的首個元素為 1；
如果 (n?1)!<k≤2?(n?1)!，我們就可以確定排列的首個元素為 2；
?

具體實現(xiàn)及注釋：

class Solution {public String getPermutation(int n, int k) {//這個是計算階乘int[] keyInfomation = new int[n+1];keyInfomation[0] = 1;//標(biāo)記是否使用boolean[] flags = new boolean[n+1];//記錄答案StringBuilder sb = new StringBuilder();for (int i = 1; i <= n; i++) {keyInfomation[i] = i * keyInfomation[i-1];}//這個i代表位數(shù)，i=1說明在尋找第一位for (int i = 1; i <= n; i++) {//為什么是k-1呢。首先我們得知道為什么后面會+1，/號是向下取余，比如keyInfomation[n-i]	  //為30， k為35，那么計算結(jié)果為1，但其實應(yīng)該是2，不足應(yīng)該向上取，所以最后我們需要加//1。但是這樣又會出現(xiàn)特殊情況，那就是keyInfomation[n-i]和k相等的時候，如此計算得2，又//與實際需求不符，這時候減1再除就滿足題意了int count = (k-1) / keyInfomation[n-i] + 1;//因為通過count我們已經(jīng)確定了是第幾個數(shù)放在i這個位置上，我們通過這個循環(huán)遍歷尋找這個數(shù)for (int j = 1; j <=n; j++) {//用過的數(shù)字if (flags[j] == true) continue;//先減再判斷count--;if (count != 0) {continue;}sb.append(j+"");flags[j] = true;//防止再遍歷后面break;}//這個取模是為了便于計算，相當(dāng)于把前面已經(jīng)確定的節(jié)點忽略掉，專心尋找下一個點。//這兒為什么需要k-1再去模在加一呢，其實如果k ！= keyInfomation[n-i]時候，下面這個式子//和k直接模keyInfomation[n-i]結(jié)果是一樣的，但是當(dāng)k等于keyInfomation[n-i]，實際我們需要//的是keyInfomation[n-i]或者k，而不是0。這是一種極限情況。比如我們確定i位上的數(shù)字為//5，當(dāng)k等于keyInfomation[n-i]的時候，代表5確定在i位上的最后一個排列，也是最大的一個//排列，k再多一個，在i這個位置的數(shù)字就要取下一個。如果直接模的話，結(jié)果為0，就成了5//在i為上的第一個排列，也就是最小的排列，不合題意k = (k-1) % keyInfomation[n-i] + 1;}return sb.toString();}
}