-
Notifications
You must be signed in to change notification settings - Fork 0
/
169.swift
54 lines (50 loc) · 1.32 KB
/
169.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// passed
// 普通方法
class Solution1 {
func majorityElement(_ nums: [Int]) -> Int {
// 遍历一遍,给出现最多的数字计数
// 只会有一个数满足条件
// O(n)空间复杂度
var lookup = [Int: Int]()
for n in nums {
lookup[n, default: 0] += 1
}
return lookup.first { $0.value > nums.count / 2 }!.key
}
}
// Boyer-Moore Voting Algorithm
class Solution {
func majorityElement(_ nums: [Int]) -> Int {
var cur = 0
var candidate = nums[0]
var count = 1
while cur < nums.count - 1 {
cur += 1
count += nums[cur] == candidate ? 1 : -1
if count == 0 { // count == 0 时必然还有剩余
cur += 1
candidate = nums[cur]
count = 1
}
}
return candidate
}
}
// 别人的更简洁的实现
class Solution {
func majorityElement(_ nums: [Int]) -> Int {
var count = 0
var current = nums[0]
for i in 0..<nums.count {
if count == 0 {
current = nums[i]
count += 1
} else if current == nums[i] {
count += 1
} else {
count -= 1
}
}
return current
}
}