[Swift]LeetCode229. 求众数 II | Majority Element II_app

概述Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. Note: The algorithm should run in linear time and in O(1) space. Example 1: Input: [3,2,3]Output: [3] Example

Given an integer array of size n,find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

input: [3,2,3]Output: [3]

Example 2:

input: [1,1,3,2]Output: [1,2]

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1:

输入: [3,3]输出: [3]

示例 2:

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

96ms

 1 class Solution { 2     func majorityElement(_ nums: [Int]) -> [Int] { 3         guard nums.count > 1 else { 4             return nums 5         } 6          7         var majorA = nums[0] 8         var countA = 0 9         10         var majorB = nums[0]11         var countB = 012         13         for index in 0...(nums.count-1) {14             if nums[index] == majorA {15                 countA += 116                 continue17             } 18             19             if nums[index] == majorB {20                 countB += 121                 continue22             }23             24             if countA == 0 {25                 majorA = nums[index]26                 countA += 127                 continue28             }29             30             if countB == 0 {31                 majorB = nums[index]32                 countB += 133                 continue34             }35 36             countA -= 137             countB -= 138         }39         40         countA = 041         countB = 042         for index in 0...(nums.count - 1) {43             if nums[index] == majorA {44                 countA += 145             } else if nums[index] == majorB {46                 countB += 147             }48         }49                 50         var result = [Int]()51         if countA > nums.count/3 {52             result.append(majorA)53         }54         if countB > nums.count/3 {55             result.append(majorB)56         }57         58         return result59     }60 }

104ms

 1 class Solution { 2     func majorityElement(_ nums: [Int]) -> [Int] { 3  4         var res = [Int]() 5         var cm = 0,cn = 0,m = 0,n = 0 6         for a in nums { 7             if a == m { cm += 1 } 8             else if a == n { cn += 1 } 9             else if cm == 0 { m = a; cm = 1}10             else if cn == 0 { n = a; cn = 1 }11             else { cm -= 1; cn -= 1}12         }13         cm = 0; cn = 014         for a in nums {15             if a == m { cm += 1 }16             else if a == n { cn += 1 }17         }18         if cm > nums.count / 3 {res.append(m)}19         if cn > nums.count / 3 {res.append(n)}20         return res21     }22 }

112ms

 1 class Solution { 2     func majorityElement(_ nums: [Int]) -> [Int] { 3         var elems: [Int: Int] = [:] 4         for n in nums { 5             elems[n,default: 0] +=  1 6         } 7         return elems.compactMap { key,value in  8             if value > nums.count / 3 { return key }  9             return nil 10         }11     }12 }

112ms

 1 class Solution { 2     func majorityElement(_ nums: [Int]) -> [Int] { 3         var dict:[Int : Int] = [Int:Int]() 4         for num in nums { 5             if let n = dict[num] { 6                 dict[num] = n + 1 7             } else { 8                 dict[num] = 1 9             }10         }11         var r = [Int]()12         let m = nums.count / 313         for (k,v) in dict {14             if v > m {15               r.append(k)16             }17         }18         return r19     }20 }

116ms

 1 class Solution { 2     func majorityElement(_ nums: [Int]) -> [Int] { 3          4         if nums.count == 0 { 5             return [] 6         } 7          8         var dict: [Int: Int] = [:] 9         var resultList: Set<Int> = []10         let limit = nums.count/311         12         for number in nums {13             var result = 114             if let temp = dict[number] {15                 result = temp + 116             }17             dict[number] = result18             19             if result > limit {20                 resultList.insert(number)21             }22         }23         24         return Array(resultList)25     }26 }

124ms

 1 class Solution { 2     func majorityElement(_ nums: [Int]) -> [Int] { 3          4         if nums.count == 0 { 5             return [] 6         } 7          8         var dict: [Int: Int] = [:] 9         var resultList: [Int] = []10         let limit = nums.count/311         12         for number in nums {13             var result = 114             if let temp = dict[number] {15                 result = temp + 116             }17             dict[number] = result18             19             if result > limit && !resultList.contains(number){20                 resultList.append(number)21             }22         }23         24         return resultList25     }26 }

140ms

 1 class Solution { 2     func majorityElement(_ nums: [Int]) -> [Int] { 3         var dict = [Int: Int]()  4         var r = [Int]() 5         for n in nums { 6             dict[n,default: 0] += 1 7             if dict.keys.count == 3 { 8                 for key in dict.keys { 9                     dict[key,default: 0] -= 110                     if dict[key,default: 0] == 0 {11                         dict[key] = nil12                     }13                 }14             }15         }16         let c = nums.reduce(into: [Int: Int]()){ $0[$01,default: 0] += 1 }17         return Array(dict.keys).filter { c[$0,default: 0] > nums.count / 3 }18     }19 }

156ms

 1 class Solution { 2    func majorityElement(_ nums: [Int]) -> [Int] { 3         var res = [Int:Int].init() 4          5         for i in 0..<nums.count { 6             if res.keys.contains(nums[i]){ 7                 let value = res[nums[i]]!+1 8                 res[nums[i]] = value 9             }else{10                 res[nums[i]] = 111             }12         }13         14         let dict = res.filter { (arg) -> Bool in15             16             let (_,value) = arg17             return value > nums.count/318         }19         return Array(dict.keys)20     }21 }