[Swift]LeetCode90.子集II|SubsetsII

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

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

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

12ms

 1 class Solution {
 2     func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
 3         
 4         var result = [[Int]]()
 5         var temp = [Int]()
 6         
 7         var sortedNums = nums.sorted()
 8         
 9         backTrack(sortedNums, &result, &temp, 0)
10         return result
11     }
12     
13     func backTrack(_ nums: [Int], _ result: inout [[Int]], _ temp: inout [Int], _ start: Int) {
14         guard start <= nums.count else {return}
15         result.append(temp)
16         for i in start ..< nums.count {
17             if i > start && nums[i] == nums[i - 1] {continue}
18             temp.append(nums[i])
19             backTrack(nums, &result, &temp, i + 1)
20             temp.removeLast()
21         }
22     }
23 }

12ms

 1 class Solution {
 2     func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
 3         
 4         let nums = nums.sorted()
 5         var result: [[Int]] = [[]]
 6         
 7         var index = 0
 8         
 9         while index < nums.count {
10             print(index)
11             
12             var dupCount = 0
13             
14             for dupIndex in index..<nums.count {
15                 if nums[dupIndex] == nums[index] {
16                     dupCount += 1
17                 } else {
18                     break
19                 }
20             }
21             
22             let existSubSets = result
23             for existSubset in existSubSets {
24                 var subset = existSubset
25                 for _ in 0..<dupCount {
26                     subset.append(nums[index])
27                     result.append(subset)
28                 }
29             }
30             index += dupCount
31         }
32         return result
33     }
34 }

16ms

 1 class Solution {
 2     func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
 3         
 4         if nums.count == 0 {
 5             return []
 6         }
 7         
 8         var nums = nums.sorted()
 9         var result = [[Int]]()
10         result.append([])
11         var size = 1, last = nums[0]
12         for i in 0..<nums.count {
13             if last != nums[i] {
14                 last = nums[i]
15                 size = result.count
16             }
17             let newSize = result.count
18             for j in newSize - size..<newSize {
19                 var out = result[j] + [nums[i]]
20                 result.append(out)
21             }
22         }
23         return result
24     }
25 }

96ms

 1 class Solution {
 2     func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
 3         guard !nums.isEmpty else {
 4             return []
 5         }
 6         var sorted = nums
 7         sorted.sort(by:<)
 8         var result = [[Int]]()
 9         for num in sorted {
10             for i in 0..<result.count {
11                 var item = result[i]
12                 item.append(num)
13                 if !result.contains(item) {
14                     result.append(item)
15                 }
16 
17             }
18             var newArray = [num]
19             if !result.contains(newArray) {
20                 result.append(newArray)
21             }   
22         }
23         result.append([])
24         return result
25     }
26 }

132ms

 1 class Solution {
 2     
 3 func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
 4      let nums = nums.sorted()
 5     var r = [[Int]]()
 6      subsetsWithDuph(nums, 0,[Int](),&r)
 7     return r
 8 }
 9     func subsetsWithDuph(_ nums: [Int], _ i:Int,_ tep:[Int], _ r:inout [[Int]]){
10         
11         if i == nums.count-1 {
12             var tep = tep
13             if (!r.contains(tep)) {
14                 r.append(tep)
15             }
16             
17             tep.append(nums[i])
18             
19             if (!r.contains(tep)) {
20                 r.append(tep)
21             }           
22             return
23         }
24         var tep = tep
25         subsetsWithDuph(nums,i+1,tep,&r)
26         tep.append(nums[i])
27         subsetsWithDuph(nums,i+1,tep,&r)
28     }
29 }

136ms

 1 class Solution {
 2     func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
 3         var result = [[Int]()]
 4         guard nums.count > 0 else { return result }
 5         
 6         func test(_ array: [[Int]], _ current: Int) -> [[Int]] {
 7             var result = array
 8             for temp in array {
 9                 var a = temp
10                 a.append(current)
11                 if !result.contains(a) {
12                     result.append(a)    
13                 }
14             }
15             return result
16         }
17         
18         for num in nums.sorted() {
19             result = test(result, num)
20         }
21         return result
22     }
23 }