A map counts
Count every value in one pass, then pick the most common. About 8 minutes.
A map keeps a note next to each key
A class election: the teacher reads out the votes, and next to each name on the board makes a tally. That board is a map. Each key (a name) has a value next to it (the tally so far).
A map, also called a dictionary, is a set that stores something next to every key. Finding a key and updating its value both take about one step, thanks to hashing.
counts = {3: 1}
Count everything in one walk
Walk the list once. For each value, add 1 to its tally. A value you haven't seen yet has no tally, so treat it as 0 first. When the walk ends, the map holds every value's count.
Then read off the winner. When two values tie, the problem needs a rule to break it: here the smaller value wins.
counts = {}
for x in nums:
counts[x] = counts.get(x, 0) + 1
top = max(counts.values())
tied = [x for x in counts
if counts[x] == top]
return min(tied)After counting 6, 2, 6, 2, 9, what does the map hold?
- A6 → 2, 2 → 2, 9 → 1
- B0 → 6, 1 → 2, 2 → 6, …
- CJust 6, 2, 9
Show the answer
6 → 2, 2 → 2, 9 → 1. 6 and 2 appear twice each, 9 once.
Most frequent value
Return the value that appears most often in nums. If several values tie for the most, return the smallest of them. nums is never empty.
nums = [3, 1, 3, 2, 3] → 3
1 ≤ n ≤ 500,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000