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 基础为核心的技术内容，也整理收集优秀的学习资料。