169. Majority Element & 229. Majority Element II
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3] Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2] Output: 2
class Solution {
public int majorityElement(int[] nums) {
Map<Integer,Integer> countMajority = new HashMap<>();
for(int num : nums){
countMajority.put(num,countMajority.getOrDefault(num,0)+1);
}
for(int num : nums){
if(countMajority.get(num) > nums.length/2){
return num;
}
}
return -1;
}
}
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 = -1;
int ele2 = -1;
int cnt1 = 0;
int cnt2 = 0;
for(int num : nums){
if(num == ele1){
cnt1++;
}else if(num == ele2){
cnt2++;
}else if(cnt1 == 0){
ele1 = num;cnt1++;
}else if(cnt2 == 0){
ele2 = num;cnt2++;
}else{
cnt1--;
cnt2--;
}
}
List<Integer> res = new ArrayList<>();
cnt1 = 0;
cnt2 = 0;
for(int num : nums){
if(num == ele1) cnt1++;
if(num == ele2) cnt2++;
}
if(cnt1 > nums.length/3) res.add(ele1);
if(cnt2 > nums.length/3 && ele1 != ele2) res.add(ele2);
if(res.size() == 2 && res.get(0)>res.get(1)){
int temp = res.get(0);
res.set(0,res.get(1));
res.set(1,temp);
}
return res;
}
}
Comments
Post a Comment