• LeetCode 60.第k個排列
  給出集合 [1,2,3,…,n]，其所有元素共有 n! 種排列。
  按大小順序列出所有排列情況，并一一標記，當 n = 3 時, 所有排列如下：

1. "123"2. "132"3. "213"4. "231"5. "312"6. "321" 給定 n 和 k，返回第 k 個排列。 說明：給定 n 的范圍是 [1, 9]。給定 k 的范圍是[1, n!]。 示例 1: 輸入: n = 3, k = 3 輸出: "213"示例 2: 輸入: n = 4, k = 9 輸出: "2314"

題目分析:

本題采用數學中的方法，依次找到第k個序列的第一位數，第二位數…

本題使用list來存儲集合中的元素，方便數字直接移除，使用StringBuilder類型的數據s來存儲結果序列(因為StringBuilder是可變的字符串類型)。因為數組的下標是從0開始的，所以一開始的k=k-1,然后開始依次找到結果序列的第一個數的下標，找到之后將該下標所對的數加在s中，然后在list中移除該數。重復上一步，直到最后數組為空。

進行的循環次數是n次，循環的結束條件是n<=0時就跳出循環，此時序列中的所有數字都已經移除完畢，則結果序列已經生成。

舉例分析如下：n=3,k=3

1+對2,3的全排列(2!) k=k-1=2index=k/fac(n-1)=k/2!=1,1所對的下標是2 k=k-index*fac(n-1)=2-2=0,0所對的下標是1 2+對1,3的全排列(2!)----------------------------------->2,1+對3的全排列(1!)-------------------------------------->213 2,3+對1的全排列(1!) 3+對1,2的全排列(2!)

代碼:

class Solution {public int fac(int n){ //求階乘int result=1;for(int i=2;i<=n;i++){result*=i;}return result;}public String getPermutation(int n, int k) {List<Integer> list = new ArrayList<Integer>();StringBuilder s = new StringBuilder();for (int i=1;i<=n;i++){list.add(i);}k-=1;//因為從0開始計數，所以位數需要減1while(n>0){int index = k/fac(n-1);//找到第k個序列的每一位數的依次的索引下標s.append(list.remove(index));k=k-index*fac(n-1);n=list.size();}return s.toString();} }

總結

以上是生活随笔為你收集整理的leetcode60.第k个排列java题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。