LeetCode 60. Permutation Sequence 全排列序列LeetCode-Go 倉庫 DFS 解法源碼級解析【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go導讀本文以 LeetCode-Go 倉庫中 60. Permutation Sequence 題解文檔為主線完整還原題目定義、約束條件與示例并深入解析倉庫中 DFS 暴力枚舉實現 60. Permutation Sequence.go 的每一行邏輯與復雜度成因。讀完后你將掌握「按字典序求第 k 個全排列」的 DFS 回溯寫法、其 O(n!) 時間代價的由來以及題解文檔中點名提示的「更優解法」——基于階乘數系統的逐位構造法。一、題目理解什么是第 k 個排列集合[1, 2, 3, ..., n]中所有元素共能組成n! 種不重復的排列。將這些排列按字典序大小順序列出并逐一編號第 k 個就是題目要求的輸出。以 n 3 為例全部 6 種排列按序排列為123132213231312321給定 n 和 k返回第 k 個排列序列。約束條件n 的取值范圍為1 到 9含端點k 的取值范圍為1 到 n!含端點。這一約束意味著 n 最大為 9n! 最大為 362880暴力枚舉在最壞情況下要遍歷 36 萬量級的葉子節點仍是可運行但明顯低效的規模——這正是題解文檔提示「想想更優的解法」的原因。官方示例示例 1Input: n 3, k 3 Output: 213示例 2Input: n 4, k 9 Output: 2314可以從 n 3 的排列表中直接驗證示例 1第 3 個排列正是213。示例 2 需要 n 4 的字典序全排列表共 24 種第 9 個為2314。二、題目大意給出集合[1, 2, 3, …, n]其所有元素共有 n! 種排列。按大小順序列出所有排列情況并一一標記當 n 3 時所有排列依次為123、132、213、231、312、321。給定 n 和 k返回第 k 個排列。本質上這是一道「全排列生成 字典序截斷」的題目要么老老實實生成全部排列并數到第 k 個DFS 暴力法要么利用排列數與階乘之間的數學關系直接定位每一位階乘數系統法。三、解題思路DFS 暴力枚舉倉庫給出的解法題解文檔在「解題思路」一節給出的核心策略是用 DFS 暴力枚舉這種做法時間復雜度特別高想想更優的解法。也就是說倉庫選擇先用正確但低效的方案打開思路從空排列出發用深度優先搜索逐位填充數字used數組標記已用數字每生成一個完整排列深度達到 n就令計數器 k 減一當 k 減到 0 時當前排列即為第 k 個排列立即停止。這種寫法把「第 k 個」轉化為「深度優先遍歷順序中的第 k 個葉子節點」依靠 DFS 天然按字典序訪問葉子節點的性質無需額外排序。四、源碼解析逐行拆解 DFS 實現倉庫中的實際實現位于 60. Permutation Sequence.go完整代碼如下與題解文檔 0060.Permutation-Sequence.md 中的代碼一致package leetcode import ( fmt strconv ) func getPermutation(n int, k int) string { if k 0 { return } used, p, res : make([]bool, n), []int{}, findPermutation(n, 0, k, p, res, used) return res } func findPermutation(n, index int, k *int, p []int, res *string, used *[]bool) { fmt.Printf(n %v index %v k %v p %v res %v user %v\n, n, index, *k, p, *res, *used) if index n { *k-- if *k 0 { for _, v : range p { *res strconv.Itoa(v 1) } } return } for i : 0; i n; i { if !(*used)[i] { (*used)[i] true p append(p, i) findPermutation(n, index1, k, p, res, used) p p[:len(p)-1] (*used)[i] false } } return }4.1 入口函數getPermutationfunc getPermutation(n int, k int) string { if k 0 { return } used, p, res : make([]bool, n), []int{}, findPermutation(n, 0, k, p, res, used) return res }used長度為 n 的布爾數組used[i] true表示數字i1已被選用p當前路徑記錄已選數字的下標后續統一加 1 還原為真實數字res最終結果字符串通過指針傳入便于在遞歸深處直接寫入k同樣以指針傳入因為 k 在遞歸中需要被跨層級修改每找到一個完整排列就遞減if k 0 { return }對非法輸入k 0的防御性處理與測試用例{3, 0}期望輸出相對應。4.2 遞歸主體findPermutation遞歸函數的五個參數含義為參數類型含義nint排列長度數字個數indexint當前已填充的位數等于遞歸深度k*int指向剩余計數的指針葉子節點處遞減p[]int當前已選數字下標序列路徑res*string指向結果字符串的指針used*[]bool指向使用標記數組的指針遞歸終止條件if index n { *k-- if *k 0 { for _, v : range p { *res strconv.Itoa(v 1) } } return }當深度達到 n 時p已構成一個完整排列如下標[0, 1, 2]對應123。此時*k--排列計數減一表示「跳過了一個排列」若*k 0說明當前正是第 k 個排列將下標序列p逐個1并用strconv.Itoa轉成字符拼接到res無論是否命中都會return回溯繼續遍歷剩余分支——但由于命中后res已非空后續葉子節點雖然仍會被訪問此實現沒有顯式剪枝結果不會再被覆蓋。未達深度的分支選擇邏輯for i : 0; i n; i { if !(*used)[i] { (*used)[i] true p append(p, i) findPermutation(n, index1, k, p, res, used) p p[:len(p)-1] (*used)[i] false } }每層從下標 0 開始嘗試所有未使用數字保證生成順序嚴格符合字典序p append(p, i)選入當前數字遞歸進入下一層p p[:len(p)-1]與(*used)[i] false是標準的回溯撤銷操作恢復現場以嘗試下一個分支。4.3 關于代碼中的調試打印實現的第一行保留了fmt.Printf(n %v index %v k %v p %v res %v user %v\n, ...)調試輸出注意其中user為筆誤實際意圖是輸出used數組。運行時它會打印每次遞歸進入時的參數快照方便觀察 DFS 的訪問軌跡正式提交 LeetCode 時需刪除該行因為它會讓輸出與判定產生額外 IO 開銷。4.4 復雜度分析時間復雜度O(n!)。最壞情況下 k n!需要完整遍歷所有排列的葉子節點才能命中最后一個即便提前命中遍歷規模也與 k 同階整體受 n! 上界約束。空間復雜度O(n)。遞歸棧深度最大為 nused與p均為 O(n)res長度為 n無額外與排列數同階的存儲。正是由于 O(n!) 的時間代價題解文檔才明確指出「這種做法時間復雜度特別高」引導讀者思考基于階乘數系統的數學解法。五、測試用例驗證倉庫測試文件如何斷言倉庫為本題提供了單元測試 60. Permutation Sequence_test.go采用結構體切片驅動的表驅動測試模式type question60 struct { para60 ans60 } type para60 struct { n int k int } type ans60 struct { one string }測試用例共 3 組輸入(n, k)期望輸出(3, 3)213(4, 9)2314(3, 0)斷言邏輯如下for _, q : range qs { a, p : q.ans60, q.para60 got : getPermutation(p.n, p.k) if got ! a.one { t.Fatalf(input %v expected %v got %v, p, a.one, got) } fmt.Printf(【input】:%v 【output】:%v\n, p, got) }前兩組用例直接對應題目官方示例第三組(3, 0)覆蓋了入口函數if k 0的防御分支驗證非法輸入返回空串。這說明該實現不僅針對正常輸入還考慮了參數邊界的健壯性。在倉庫根目錄執行go test ./leetcode/0060.Permutation-Sequence/...即可運行該用例或參考 gotest.sh 了解倉庫整體的測試腳本約定。六、更優解法探討階乘數系統逐位定位題解文檔點名的方向題解文檔明確留下「想想更優的解法」的提示。這里的經典優化思路是階乘數系統factorial number system也稱為康托展開的逆運算不生成任何排列而是直接通過數學計算確定第 k 個排列的每一位。6.1 核心原理給定 n 個數字以第 1 位數字 d 為例若固定 d 為某個值剩余 n-1 個數字可組成(n-1)!種排列因此字典序下每 (n-1)! 個排列共享同一個首位首位確定后k 對 (n-1)! 取余并繼續在剩余 n-1 個數字中定位第 2 位依次類推。逐位推導過程為k k - 1 // 轉為 0 基索引便于整除 第 1 位下標 k / (n-1)! k k % (n-1)! 第 2 位下標 k / (n-2)! k k % (n-2)! ...其中每一步的「下標」都指向**當前剩余數字集合按升序**中的第幾個數字選完后將其從集合中移除再進入下一位。6.2 以 n 3, k 3 為例手算k 3 - 1 2剩余數字[1, 2, 3]第 1 位2 / 2! 1取剩余數字第 1 個0 基即2k 2 % 2 0剩余[1, 3]第 2 位0 / 1! 0取1k 0 % 1 0剩余[3]第 3 位取3。結果213與示例 1 及倉庫測試用例完全一致。6.3 以 n 4, k 9 為例手算k 9 - 1 8剩余[1, 2, 3, 4]第 1 位8 / 3! 1取2k 8 % 6 2剩余[1, 3, 4]第 2 位2 / 2! 1取3k 2 % 2 0剩余[1, 4]第 3 位0 / 1! 0取1剩余[4]第 4 位取4。結果2314與示例 2 及倉庫測試用例一致。6.4 兩種方法對比維度DFS 暴力枚舉倉庫實現階乘數系統逐位構造時間復雜度O(n!)O(n2)每次從剩余集合取第 i 個元素空間復雜度O(n)O(n)代碼復雜度低回溯模板直接套用中需維護階乘表與剩余數字集合適用場景理解全排列生成與回溯大規模 n 下直接命中第 k 個排列n ≤ 9 時兩者都能在毫秒級內完成但 n 一旦增大例如 n 1212! ≈ 4.79 億DFS 將完全不可行而階乘數系統依舊可以在 O(n2) 內求解。這也是 LeetCode 官方將該題定位為數學題的原因。七、小結與延伸閱讀本文圍繞 LeetCode-Go 倉庫的 0060.Permutation-Sequence.md 題解文檔完成了三件事完整復述題目字典序下第 k 個全排列的定義、n ∈ [1, 9] 與 k ∈ [1, n!] 的約束、兩個官方示例源碼級解析倉庫解法逐行拆解 60. Permutation Sequence.go 的入口函數、遞歸回溯、終止條件與復雜度并借助 60. Permutation Sequence_test.go 中的三組用例驗證正確性順著題解文檔的提示探索更優解用階乘數系統康托展開逆運算將時間復雜度從 O(n!) 降到 O(n2)并用手算驗證兩個示例。對于想繼續深入同類問題的讀者倉庫中 46. Permutations全排列回溯與 47. Permutations II含重復元素的全排列使用了相同的 DFS used回溯骨架可作為對比閱讀而本題的數學解法思路也與「按字典序排名」類問題如康托展開一脈相承。【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考