2
2
1
3
2
2
1
2
2
[0][1][2][3][4][5][6][7][8]
Brute force · hash map
▸1count ← {}2for x in arr: count[x] ← count[x] + 13return the key whose count > n / 2
state
- n9
- n/24.5
warming up the animation
Given an array of size n, return the element that appears more than ⌊n/2⌋ times. You may assume such an element always exists.
▸1count ← {}2for x in arr: count[x] ← count[x] + 13return the key whose count > n / 2
line 1Count every value, then pick the one that appears more than n/2 times.