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.
A temporary map is used to count elements. If the elemented appeared more than the max element, it will be the new most frequent element. A possible optimization is to stop once the count reaches > n/2
.