Description
https://leetcode.com/problems/majority-element-ii/
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Follow-up: Could you solve the problem in linear time and in O(1) space?
Example 1:
Input: nums = [3,2,3] Output: [3]
Example 2:
Input: nums = [1] Output: [1]
Example 3:
Input: nums = [1,2] Output: [1,2]
Constraints:
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
Explanation
Use a hashmap to store the counts of elements and find out the keys where appears more than ⌊ n/3 ⌋ times.
Python Solution
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
counter = {}
for num in nums:
counter[num] = counter.get(num, 0) + 1
results = []
for key, value in counter.items():
if value > len(nums) // 3:
results.append(key)
return results- Time Complexity: O(N).
- Space Complexity: O(N).