[Swift]LeetCode47.全排列II|PermutationsII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [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 }