# 229.Majority-Element-II

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/majority-element-ii/

## ้ข็ฎๆ่ฟฐ

``````Given an integer array of size n, find all elements that appear more than โ n/3 โ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:
Input: [3,2,3]
Output: [3]

Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]``````

## ไปฃ็ 

### Approach #1 Boyer Moore

``````class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> ans = new ArrayList<Integer>();
if (nums == null || nums.length == 0)        return ans;
int count1 = 0, count2 = 0;
int candidate1 = 0, candidate2 = 1;
for (int num: nums) {
if (num == candidate1)    count1++;
else if (num == candidate2)  count2++;
else if (count1 == 0) {
candidate1 = num;
count1 = 1;
}
else if (count2 == 0) {
candidate2 = num;
count2 = 1;
}
else {
count1--;
count2--;
}
}

count1 = 0;
count2 = 0;
for (int num: nums) {
if (num == candidate1)    count1 += 2;
else count1--;
if (num == candidate2)    count2 += 2;
else count2--;
}

return ans;
}
}``````

Last updated