【題目】
給出集合 [1,2,3,...,n]，其所有元素共有 n! 種排列绍妨。
按大小順序列出所有排列情況润脸，并一一標(biāo)記，當(dāng) n = 3 時(shí), 所有排列如下：
"123""132""213""231""312""321"
給定 n 和 k他去，返回第 k 個(gè)排列毙驯。
示例 1：
輸入： n = 3, k = 3
輸出： "213"
示例 2：
輸入： n = 4, k = 9
輸出： "2314"
示例 3：
輸入： n = 3, k = 1
輸出： "123"
提示：
1 <= n <= 91 <= k <= n!
【題目解析】
解題方法
初始化：從1到n的數(shù)字列表，用于構(gòu)建排列灾测；一個(gè)記錄階乘的數(shù)組爆价，用于快速計(jì)算不同長(zhǎng)度下的排列數(shù)。
-
尋找第k個(gè)排列：
- 對(duì)于n個(gè)數(shù)媳搪，第一個(gè)數(shù)字的位置可以通過(guò)
(k-1)/(n-1)!確定铭段，其中(n-1)!表示除第一個(gè)數(shù)字外，剩下的數(shù)字組成的排列總數(shù)秦爆。 - 確定第一個(gè)數(shù)字后序愚，從列表中移除該數(shù)字，更新
k值為k % (n-1)!等限，繼續(xù)確定下一個(gè)數(shù)字爸吮。 - 重復(fù)上述過(guò)程直到所有數(shù)字確定芬膝。
- 對(duì)于n個(gè)數(shù)媳搪，第一個(gè)數(shù)字的位置可以通過(guò)
class Solution:
def getPermutation(self, n: int, k: int) -> str:
# 階乘數(shù)組，用于計(jì)算不同位置的索引
factorial = [1] * (n + 1)
for i in range(1, n + 1):
factorial[i] = factorial[i - 1] * I
# 因?yàn)閗是從1開(kāi)始計(jì)數(shù)的形娇，我們將k轉(zhuǎn)換為從0開(kāi)始
k -= 1
# 初始化數(shù)字列表和結(jié)果字符串
nums = [str(i) for i in range(1, n + 1)]
result = ''
# 從最高位開(kāi)始確定每個(gè)位置的數(shù)字
for i in range(n, 0, -1):
# 確定當(dāng)前位置的數(shù)字
index = k // factorial[i - 1]
k %= factorial[i - 1]
# 將確定的數(shù)字加到結(jié)果字符串锰霜，并從列表中移除
result += nums.pop(index)
return result
執(zhí)行效率
image.png
【總結(jié)】
適用問(wèn)題類型
- 需要從排列組合中直接定位到特定位置的排列。
- 排列數(shù)量龐大桐早，無(wú)法直接枚舉所有排列的場(chǎng)景癣缅。
解決算法：基于階乘數(shù)系統(tǒng)的直接計(jì)算法
這種算法通過(guò)將排列問(wèn)題轉(zhuǎn)換為階乘數(shù)系統(tǒng)的問(wèn)題來(lái)解決，利用數(shù)學(xué)原理直接計(jì)算出第k個(gè)排列的具體形態(tài)勘畔。
算法特點(diǎn)
- 高效率：直接根據(jù)給定的序號(hào)k計(jì)算出排列所灸，避免了生成全部排列的巨大開(kāi)銷。
- 低空間消耗：除了最終的排列字符串炫七，算法運(yùn)行過(guò)程中僅需存儲(chǔ)階乘數(shù)值和當(dāng)前可選數(shù)字爬立，空間復(fù)雜度低。
- 易于實(shí)現(xiàn)：算法邏輯清晰万哪，易于按照步驟實(shí)現(xiàn)侠驯。
時(shí)間復(fù)雜度與空間復(fù)雜度
-
時(shí)間復(fù)雜度：
O(n^2)，主要時(shí)間開(kāi)銷在于每次從列表中移除選定的數(shù)字奕巍，需要遍歷列表吟策。 -
空間復(fù)雜度：
O(n)，需要額外空間存儲(chǔ)階乘數(shù)值和當(dāng)前可選數(shù)字列表的止。
實(shí)踐意義
這種算法為解決大規(guī)模排列問(wèn)題提供了有效的工具檩坚，尤其是在需要高效處理大量數(shù)據(jù)、直接找到解而不是枚舉所有可能的情況時(shí)诅福。在數(shù)據(jù)科學(xué)匾委、密碼學(xué)等領(lǐng)域，找到快速解決組合數(shù)學(xué)問(wèn)題的方法具有重要的應(yīng)用價(jià)值氓润。此外赂乐，學(xué)習(xí)和實(shí)現(xiàn)這種算法可以幫助提升對(duì)組合數(shù)學(xué)和算法設(shè)計(jì)的理解，增強(qiáng)解決復(fù)雜問(wèn)題的能力咖气。
