229. Majority Element II
Medium55.8% acceptance1,213,988 / 2,174,480 submissions
Asked by 11 companies
Topics
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
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
Follow up: Could you solve the problem in linear time and in O(1) space?
Hints
Hint 1
Think about the possible number of elements that can appear more than ⌊ n/3 ⌋ times in the array.
Hint 2
It can be at most two. Why?
Hint 3
Consider using Boyer-Moore Voting Algorithm, which is efficient for finding elements that appear more than a certain threshold.