-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathmajority-element.py
More file actions
83 lines (74 loc) · 2.43 KB
/
Copy pathmajority-element.py
File metadata and controls
83 lines (74 loc) · 2.43 KB
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
# 169. Majority Element
# 🟢 Easy
#
# https://leetcode.com/problems/majority-element/
#
# Tags: Array - Hash Table - Divide and Conquer - Sorting - Counting
import timeit
from collections import defaultdict
from typing import List
# The naive solution uses a hashmap to keep a count of the number of
# times that we have seen a given number, when that count becomes more
# than half the length of the input array, we return that value.
#
# Time complexity: O(n) - We visit each element once and do O(1) work.
# Space complexity: O(n) - We can end up with almost n/2 entries in the
# dictionary of frequencies.
#
# Runtime 178 ms Beats 48.64%
# Memory 15.6 MB Beats 27.36%
class Naive:
def majorityElement(self, nums: List[int]) -> int:
boundary = len(nums) // 2
freq = defaultdict(int)
for num in nums:
freq[num] += 1
if freq[num] > boundary:
return num
raise Exception("This should never run")
# For the follow-up we can use the Boyer-Moore majority vote algorithm
# https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm
#
# Time complexity: O(n) - We visit each element once and do O(1) work.
# Space complexity: O(1) - We only store two pointers.
#
# Runtime 158 ms Beats 95.23%
# Memory 15.4 MB Beats 99.25%
class BoyerMoore:
def majorityElement(self, nums: List[int]) -> int:
candidate, count = None, 0
for num in nums:
if count == 0:
candidate = num
count = 1
elif num == candidate:
count += 1
else:
count -= 1
return candidate
def test():
executors = [
Naive,
BoyerMoore,
]
tests = [
[[3, 2, 3], 3],
[[2, 2, 1, 1, 1, 2, 2], 2],
]
for executor in executors:
start = timeit.default_timer()
for _ in range(1):
for col, t in enumerate(tests):
sol = executor()
result = sol.majorityElement(t[0])
exp = t[1]
assert result == exp, (
f"\033[93m» {result} <> {exp}\033[91m for"
+ f" test {col} using \033[1m{executor.__name__}"
)
stop = timeit.default_timer()
used = str(round(stop - start, 5))
cols = "{0:20}{1:10}{2:10}"
res = cols.format(executor.__name__, used, "seconds")
print(f"\033[92m» {res}\033[0m")
test()