題目描述（中等難度）

又是一道全排列的題，之前在31題，46題，也討論過全排列問題的一些解法。這道題的話，是給一個 n，不是輸出它的全排列，而是把所有組合從從小到大排列後，輸出第 k 個。

解法一

以 n = 4 為例，可以結合下圖看一下。因為是從小到大排列，那麼最高位一定是從 1 到 4。然後可以看成一組一組的，我們只需要求出組數，就知道最高位是多少了。而每組的個數就是 n - 1 的階乘，也就是 3 的階乘 6。

算組數的時候， 1 到 5 除以 6 是 0，6 除以 6 是 1，而 6 是屬於第 0 組的，所有要把 k 減去 1。這樣做除法結果就都是 0 了。

int perGroupNum = factorial(n - 1);
int groupNum = (k - 1) / perGroupNum;

當然，還有一個問題下次 k 是多少了。求組數用的除法，餘數就是下次的 k 了。因為 k 是從 1 計數的，所以如果 k 剛好等於了 perGroupNum 的倍數，此時得到的餘數是 0 ，而其實由於我們求 groupNum 的時候減 1 了，所以此時 k 應該更新為 perGroupNum。

k = k % perGroupNum;
k = k == 0 ? perGroupNum : k;

舉個例子，如果 k = 6，那麼 groupNum = ( k - 1 ) / 6 = 0， k % perGroupNum = 6 % 6 = 0，而下次的 k ，可以結合上圖，很明顯是 perGroupNum ，依舊是 6。

結合下圖，確定了最高位屬於第 0 組，下邊就和上邊的情況一樣了。唯一不同的地方是最高位是 2 3 4，沒有了 1。所有得到 groupNum 怎麼得到最高位需要考慮下。

我們可以用一個 list 從小到大保存 1 到 n，每次選到一個就去掉，這樣就可以得到 groupNum 對應的數字了。

List<Integer> nums = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
nums.add(i + 1);
}
int perGroupNum = factorial(n - 1);
int groupNum = (k - 1) / perGroupNum;
int num = nums.get(groupNum); //根據 groupNum 得到當前位
nums.remove(groupNum);//去掉當前數字

綜上，我們把它們整合在一起。

public String getPermutation(int n, int k) {
List<Integer> nums = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
nums.add(i + 1);
}
return getAns(nums, n, k);
}

private String getAns(List<Integer> nums, int n, int k) {
if (n == 1) {
//把剩下的最後一個數字返回就可以了
 return nums.get(0) + "";
}
int perGroupNum = factorial(n - 1); //每組的個數
 int groupNum = (k - 1) / perGroupNum;
int num = nums.get(groupNum);
nums.remove(groupNum);
k = k % perGroupNum; //更新下次的 k
 k = k == 0 ? perGroupNum : k;
return num + getAns(nums, n - 1, k);
}
public int factorial(int number) {
if (number <= 1)
return 1;
else
return number * factorial(number - 1);
}

時間複雜度：

空間複雜度：

這是最開始自己的想法，有 3 點可以改進一下。

第 1 點，更新 k 的時候，有一句

k = k % perGroupNum; //更新下次的 k
k = k == 0 ? perGroupNum : k;

很不優雅了，問題的根源就在於問題給定的 k 是從 1 編碼的。我們只要把 k - 1 % perGroupNum，這樣得到的結果就是 k 從 0 編碼的了。然後求 groupNum = (k - 1) / perGroupNum; 這裡 k 也不用減 1 了。

第 2 點，這個演算法很容易改成改成迭代的寫法，只需要把遞歸的函數參數， 在每次迭代更新就夠了。

第 3 點，我們求 perGroupNum 的時候，每次都調用了求迭代的函數，其實沒有必要的，我們只需要一次循環求出 n 的階乘。然後在每次迭代中除以 nums 的剩餘個數就夠了。

綜上，看一下優化過的代碼吧。

public String getPermutation(int n, int k) {
List<Integer> nums = new ArrayList<Integer>();
int factorial = 1;
for (int i = 0; i < n; i++) {
nums.add(i + 1);
if (i != 0) {
factorial *= i;
}
}
factorial *= n; //先求出 n 的階乘
 StringBuilder ans = new StringBuilder();
k = k - 1; // k 變為 k - 1
 for (int i = n; i > 0; i--) {
factorial /= (nums.size()); //更新為 n - 1 的階乘
 int groupNum = k / factorial;
int num = nums.get(groupNum);
nums.remove(groupNum);
k = k % factorial;
ans.append(num);

}
return ans.toString();
}

時間複雜度：O（n），當然如果 remove 函數的時間是複雜度是 O（n），那麼整體上就是 O（n2）。

空間複雜度：O（1）。

總

這道題其實如果寫出來，也不算難，優化的思路可以瞭解一下。


推薦閱讀：
相關文章