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.
Input: nums = [3,2,3] Output: 3
Input: nums = [2,2,1,1,1,2,2] Output: 2
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
There are many different ways to solve this problem. We’ll take a look at two of the simplest approaches. We can use a hash map to keep track of the frequency of each number or we could sort the list and return the middle value.
Note: Since we know that the majority element appears more than
n/2 times in the list, we know that it will make up more than 50% of the elements in the array. Consequently, the middle element
n//2 will always be the majority element.
Hash Map Solution
from collections import Counter class Solution: def majorityElement(self, nums: List[int]) -> int: """ T: O(N) S: O(N) """ n = len(nums) mp = Counter(nums) for number, frequency in mp.items(): if frequency > (n // 2): return number
from collections import Counter class Solution: def majorityElement(self, nums: List[int]) -> int: """ T: O(N log N) S: O(1) ~ best case; O(N) ~ worst case """ n = len(nums) nums = sorted(nums) return nums[n // 2]