0229. Majority Element II
https://leetcode.com/problems/majority-element-ii
Description
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
ac1 Boyer-Moore Algorithm
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
// corner case
if (nums.length == 0) return res;
// at most 2 majority. pass1: filter out majorities. pass2: recount numbers
// pass1: filter out majorities
int m1 = nums[0], m2 = nums[0], cnt1 = 0, cnt2 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == m1) {
cnt1++;
} else if (nums[i] == m2) {
cnt2++;
} else if (cnt1 == 0) {
m1 = nums[i];
cnt1++;
} else if (cnt2 == 0) {
m2 = nums[i];
cnt2++;
} else {
cnt1--;
cnt2--;
}
}
// pass2
cnt1 = 0; cnt2 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == m1) cnt1++;
else if (nums[i] == m2) cnt2++;
}
// Determine
if (cnt1 > nums.length/3) res.add(m1);
if (cnt2 > nums.length/3) res.add(m2);
return res;
}
}
Last updated
Was this helpful?