?LeetCode刷題實戰(zhàn)60：第k個排列
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?第k個排列，我們先來看題面：
https://leetcode-cn.com/problems/permutation-sequence/
The set [1,2,3,...,n] contains a total of n! unique permutations.
題意
樣例
示例 1:
輸入: n = 3, k = 3
輸出: "213"
示例 2:
輸入: n = 4, k = 9
輸出: "2314"
解題
n = 3, k = 3num = [1, 2, 3]這三個數(shù)組成!"123""132""213""231""312""321"
1,后面有組成兩個數(shù)123,132,可以組成2個數(shù).當首數(shù)字為2,3同樣都是.k = 3的數(shù)字 ,我們只需要?3/2?便可找到首數(shù)字什么,class?Solution?{
????public?String getPermutation(int?n, int?k) {
????????Listnum = new?ArrayList<>();
????????for?(int?i = 1; i <= n; i++) num.add(i);
????????int[] factorial = new?int[n];
????????factorial[0] = 1;
????????for?(int?i = 1; i < n; i++) factorial[i] = i * factorial[i-1];
????????n--;
????????StringBuilder res = new?StringBuilder();
????????while?(n >= 0){
????????????int?t = factorial[n];
????????????int?loc = (int) (Math.ceil((double) k / (double) t)) - 1;
????????????if?(loc == -1) loc = num.size() - 1;
????????????res.append(num.get(loc));
????????????num.remove(loc);
????????????k %= t;
????????????n--;
????????}
????????return?res.toString();
????}
}
上期推文：