LeetCode-in-Java
229. Majority Element II
Medium
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?
Solution
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> results = new ArrayList<>();
int len = nums.length;
int first = 0;
int second = 1;
int count1 = 0;
int count2 = 0;
// now we have two candidates(any integer can be chosed as),and their votes are
// zero.
for (int temp : nums) {
if (temp == first) {
count1++;
} else if (temp == second) {
count2++;
} else if (count1 == 0) {
first = temp;
count1++;
} else if (count2 == 0) {
second = temp;
count2++;
} else {
// otherwise,if one of the vote is zero,that's meaning that
// we only have or even don't have a candidate.So we set the number to the
// candidate.
count1--;
count2--;
}
// where we have two candidates whose votes bigger than zero,
// but the current number is not one of them.Votes decrease by 1 and
// the current number complete its "mission" and is skipped at the same time.
// once the cycle finished,the target is left after all the counteraction,as its
// count is bigger than n/3.
}
count1 = 0;
count2 = 0;
for (int temp : nums) {
// check both of them is bigger than n/3.Becasue we may have only one satisfying
// the demand.
if (temp == first) {
count1++;
}
if (temp == second) {
count2++;
}
}
if (count1 > len / 3) {
results.add(first);
}
if (count2 > len / 3) {
results.add(second);
}
return results;
}
}