求衆數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 }