• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode47.全排列II|PermutationsII

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/9907631.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

给定一个可包含重复数字的序列,返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

20ms
 1 class Solution {
 2     func permuteUnique(_ nums: [Int]) -> [[Int]] {
 3         var ans = [[Int]]()
 4         var nums = nums
 5         permuteUnique(&nums, 0, &ans)
 6         return ans
 7     }
 8     
 9     func permuteUnique(_ nums: inout [Int], _ startIndex: Int, _ ans: inout [[Int]]) {
10         if startIndex >= nums.count {
11             ans.append(nums)
12         }
13         
14         var visited = Set<Int>()
15         for index in startIndex..<nums.count {
16             if visited.insert(nums[index]).inserted {
17                 nums.swapAt(startIndex, index)
18                 permuteUnique(&nums, startIndex+1, &ans)
19                 nums.swapAt(startIndex, index)    
20             }
21         }
22     }
23 }

24ms

 1 class Solution {
 2     func permuteUnique(_ nums: [Int]) -> [[Int]] {
 3         let sortedNums = nums.sorted()
 4         
 5         var temp = [Int]()
 6         var result = [[Int]]()
 7         var isvisited = Array(repeating: false, count: nums.count)
 8         
 9         backTracking(sortedNums, &result, &temp, &isvisited)
10         return result 
11     }
12     
13     func backTracking(_ nums: [Int], _ result: inout [[Int]], _ temp: inout [Int], _ isvisited: inout [Bool]) {
14         if temp.count == nums.count {
15             result.append(temp)
16             return
17         }
18         
19         for i in 0 ..< nums.count where !isvisited[i] {
20             if i > 0 && nums[i] == nums[i - 1] && !isvisited[i - 1]{  
21                 continue
22             }
23             temp.append(nums[i])
24             isvisited[i] = true
25             backTracking(nums, &result, &temp, &isvisited)
26             isvisited[i] = false
27             temp.removeLast()
28         }
29         
30         
31     }
32 }

44ms

 1 class Solution {
 2     private func backtrack(_ nums: [Int], _ begin: Int,  results: inout [[Int]]) {
 3         if begin == nums.count - 1 {
 4             results.append(nums)
 5             return
 6         }
 7 
 8         var nums = nums
 9 
10         for i in begin..<nums.count {
11             if i == begin || nums[i] != nums[begin]  {
12                 nums.swapAt(begin, i)
13                 backtrack(nums, begin + 1, results: &results)
14             }
15         }
16     }
17     
18     func permuteUnique(_ nums: [Int]) -> [[Int]] {
19         var results = [[Int]]()
20         var nums = nums.sorted()
21         backtrack(nums, 0, results: &results)
22         return results
23     }
24 }

56ms

 1 class Solution {
 2     func permuteUnique(_ nums: [Int]) -> [[Int]] {
 3         var res = [[Int]]()
 4         var index = 0
 5         var nums = nums
 6         helper(&res, index, &nums)
 7         return res
 8     }
 9     
10     
11     private func helper(_ res: inout [[Int]], _ index: Int, _ nums: inout [Int]) {
12         if index == nums.count {
13             res.append(nums)
14             return
15         }
16         
17         var usedSet = Set<Int>()
18         for i in index..<nums.count {
19             if usedSet.contains(nums[i]) {
20                 continue
21             }
22             
23             usedSet.insert(nums[i])
24             nums.swapAt(index, i)
25             helper(&res, index + 1, &nums)
26             nums.swapAt(index, i)
27         }
28     }
29 }

60ms

 1 class Solution {
 2     var result = [[Int]]()
 3     func permuteUnique(_ nums: [Int]) -> [[Int]] {
 4         var nums = nums
 5         permute(&nums)
 6       return result
 7     }
 8     func permute(_ nums: inout [Int], _ index: Int = 0) {
 9       if index == nums.count{
10             result.append(nums) 
11           return
12       }
13         for i in index..<nums.count{
14             if shouldSwap(nums, index, i){
15                 nums.swapAt(index, i)
16                 permute(&nums, index+1)
17                 nums.swapAt(index, i) 
18             }
19         }
20     }    
21     
22     func shouldSwap(_ nums:[Int],_ start: Int,_ current: Int) -> Bool{
23         for i in start..<current{
24             if nums[i] == nums[current]{
25                 return false
26             }
27         }
28         return true
29     }
30 }

76ms

 1 class Solution {
 2     func permuteUnique(_ nums: [Int]) -> [[Int]] {
 3 
 4         var res = [[Int]]()
 5         var path = [Int]()
 6         let nums = nums.sorted()
 7         var isVisited = [Bool](repeating:false,count:nums.count)
 8         dfs(&res,&path,&isVisited,nums)
 9         return res
10     }
11 
12     func dfs(_ res:inout [[Int]],_ path:inout [Int],_ isVisited:inout [Bool],_ nums:[Int]) {
13         if path.count == nums.count {
14             res.append(path)
15             return
16         }
17 
18         for (i,num) in nums.enumerated() {
19             if isVisited[i] || (i > 0 && nums[i] == nums[i-1] && !isVisited[i-1]) {
20                 continue
21             }
22 
23                 path.append(num)
24                 isVisited[i] = true
25                 dfs(&res,&path,&isVisited,nums)
26                 isVisited[i] = false
27                 path.removeLast()
28 
29         }
30     }
31 
32     func toString(_ array:[Int]) -> String {
33         var str = ""
34         for (i,num) in array.enumerated() {
35             str = str + "\(num)"
36         }
37 
38         return str
39     }
40 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode1185.一周中的第几天|DayoftheWeek发布时间:2022-07-13
下一篇:
【原】iOS学习之Swift之语法2(精简版)发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap