Description
Given an integer array of size n, find all elements that appear more than n/3 times. Use Boyer-Moore voting algorithm for O(1) space.
Examples
Input:
nums = [3,2,3]Output:
[3]Explanation:
Only 3 appears more than n/3 times.
Input:
nums = [1,1,1,3,3,2,2,2]Output:
[1,2]Explanation:
Array length is 8, so n/3 = 8/3 = 2.67. Elements must appear more than 2.67 times (at least 3 times). Element 1 appears 3 times, element 2 appears 3 times, and element 3 appears 2 times. Only 1 and 2 qualify.
Input:
nums = [2,2,1,1,1,2,2]Output:
[2]Explanation:
Array length is 7, so n/3 = 7/3 = 2.33. Elements must appear more than 2.33 times (at least 3 times). Element 2 appears 4 times and element 1 appears 3 times. Only element 2 appears more than n/3 times.
Constraints
- •
1 ≤ nums.length ≤ 5 × 10⁴