LeetCode

2022-09-15數碼

前言

我們社區陸續會將顧毅（ Netflix 增長黑客，【iOS 面試之道】作者，ACE 職業健身教練。 ）的 Swift 演算法題題解整理為文字版以方便大家學習與閱讀。

LeetCode 演算法到目前我們已經更新了 46 期，我們會保持更新時間和進度（ 周一、周三、周五早上 9:00 釋出 ），每期的內容不多，我們希望大家可以在上班路上閱讀，長久積累會有很大提升。

不積跬步，無以至千裏；不積小流，無以成江海，Swift社區伴你前行。 如果大家有建議和意見歡迎在文末留言，我們會盡力滿足大家的需求。

難度水平：中等

1. 描述

給定一個可包含重復數碼的序列 nums ， 按任意順序 返回所有不重復的全排列。

2. 範例

範例 1

輸入：nums = [1,1,2] 輸出： [[1,1,2], [1,2,1], [2,1,1]]

範例 2

輸入：nums = [1,2,3] 輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

約束條件：


 1 <= nums.length <= 8


 -10 <= nums[i] <= 10

3. 答案

class PermutationsII { func permuteUnique ( _ nums : [ Int ]) -> [[ Int ]] { var res = [[ Int ]](), path = [ Int ](), visited = [ Bool ]( repeating : false , count : nums . count ) let nums = nums . sorted ( by : < ) _dfs (& res , & path , nums , & visited ) return res } private func _dfs ( inout res : [[ Int ]], inout _ path : [ Int ], _ nums : [ Int ], inout _ visited : [ Bool ]) { // termination case if path . count == nums . count { res . append ( path ) return } for i in 0. .< nums . count { if visited [ i ] || ( i > 0 && nums [ i ] == nums [ i - 1 ] && visited [ i - 1 ]) { continue } path . append ( nums [ i ]) visited [ i ] = true _dfs (& res , & path , nums , & visited ) visited [ i ] = false path . removeLast () } } }

主要思想：經典深度優先搜尋，采用最後出現避免重復。

時間復雜度： O(n^n)

空間復雜度： O(n)

該演算法題解的倉庫：LeetCode-Swift

點選前往 LeetCode 練習

關於我們

我們是由 Swift 愛好者共同維護，我們會分享以 Swift 實戰、SwiftUI、Swift 基礎為核心的技術內容，也整理收集優秀的學習資料。