求众数
求众数1（leetcode）
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
代码实现：
1 func majorityElement(_ nums: [Int]) -> Int {
2 var dict = [Int: Int]()
3 var num = nums[0]
4 for i in nums {
5 if dict[i] == nil {
6 dict[i] = 1
7 }
8 else {
9 var tmp = 1 + dict[i]!
10 if tmp > nums.count/2 {
11 num = i
12 break
13 }
15 dict[i] = tmp
16 }
17 }
18
19 return num
20 }
求众数2（leetcode）
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
示例 1:
输入: [3,2,3]
输出: [3]
示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]
分析：一个数组中，最多出现1个出现超过 ⌊ n/2 ⌋ 次的众数，最多出现2个出现超过 ⌊ n/3 ⌋ 次的众数
提示：摩尔投票算法：简单来说摩尔投票问题，找出一组数字序列中出现次数大于总数1/2的数字（并且假设这个数字一定存在）。显然这个数字只可能有一个。摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个
代码实现：
1 func majorityElement(_ nums: [Int]) -> [Int] {
2 if nums.count < 2 {
3 return nums
4 }
5
6 var m = 0, mc = 0
7 var n = 0, nc = 0
8 for i in nums {
9 if i == m {
10 mc += 1
11 } else if i == n {
12 nc += 1
13 } else if mc == 0 {
14 m = i
15 mc += 1
16 } else if nc == 0 {
17 n = i
18 nc += 1
19 } else {
20 mc -= 1
21 nc -= 1
22 }
23 }
24
25 mc = 0
26 nc = 0
27
28 for i in nums {
29 if i == m {
30 mc += 1
31 } else if i == n {
32 nc += 1
33 }
34 }
35
36 var array = [Int]()
37 if mc > nums.count/3 {
38 array.append(m)
39 }
40
41 if nc > nums.count/3 {
42 array.append(n)
43 }
44 return array
45 }
版权声明：本文为mustard22原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。