Leetcode: Majority number
Given an array nums of size n
, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋
times. You may assume that the majority element always exists in the array.
Unfortunately, it is not clear from the description whether there are only two different numbers or multiple ones. Some of the solutions seem to suggest that there are only two different ones. The solution that I will show has a time complexity of O(n)
and a space complexity of O(n)
in the worst case, that is, if all the numbers appear exactly once.
from typing import List, Optional
class Solution:
def majorityElement(self, nums: List[int]) -> int:
m = {}
max_n = nums[0]
count_n = 1
for n in nums:
if n not in m:
m[n] = 0
m[n] += 1
if m[n] > count_n:
max_n = n
count_n = m[n]
return max_n
if __name__ == '__main__':
s = Solution().majorityElement
print(s([3,2,3]), 3)
print(s([2,2,1,1,1,2,2]), 2)
> n/2
.