Programming
Leetcode-229. Majority Element II
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]
<解題>
class Solution {
public List<Integer> majorityElement(int[] nums) {
int ele1 = 0, ele2 = 0, vote1 = 0, vote2 = 0;
for (int num: nums){
if (ele1 == num && vote1 > 0){
vote1 += 1;
} else if (ele2 == num && vote2 >0){
vote2 += 1;
} else if (vote1 == 0){
ele1 = num;
vote1 = 1;
} else if (vote2 ==0){
ele2 = num;
vote2 = 1;
} else {
vote1 -= 1;
vote2 -= 1;
}
}
int cnt1 = 0, cnt2 =0;
for (int num : nums){
if(num == ele1){
cnt1 += 1;
} else if (num == ele2){
cnt2 += 1;
}
}
List<Integer> res = new ArrayList<>();
if (cnt1 > nums.length / 3){
res.add(ele1);
}
if (cnt2 > nums.length / 3){
res.add(ele2);
}
return res;
}
}
Time Complexity : O(n) Space Complexity : O(1)