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?
class Solution {
public List<Integer> majorityElement(int[] nums) {
Map<Integer, Integer> m = new HashMap<>();
List<Integer> ans = new ArrayList<>();
for (int i : nums)
m.put(i, m.getOrDefault(i, 0) + 1);
int majorityThreshold = nums.length / 3;
for (Map.Entry<Integer, Integer> e : m.entrySet())
if (e.getValue() > majorityThreshold)
ans.add(e.getKey());
return ans;
}
}class Solution {
public List<Integer> majorityElement(int[] nums) {
int n = nums.length, major1 = Integer.MIN_VALUE, major2 = Integer.MIN_VALUE, count1 = 0, count2 = 0;
List<Integer> ans = new ArrayList<>();
for (int i : nums) {
if (count2 == 0 && i != major1) { // moore voting but ignore major1 (since both candidate shouldnt be same)
major2 = i;
count2 = 1;
} else if (count1 == 0 && i != major2) {
major1 = i;
count1 = 1;
} else if (i == major1)
count1++;
else if (i == major2)
count2++;
else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i : nums)
if (i == major1)
count1++;
else if (i == major2)
count2++;
if (count1 > n / 3)
ans.add(major1);
if (count2 > n / 3)
ans.add(major2);
return ans;
}
}