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]
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?
The solution to the above question is
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n=floor(nums.size()/3);
vector<int>ans;
int num1=-1;
int num2=-1;
int cnt1=0;
int cnt2=0;
for(int i=0; i<nums.size(); i++){
if(nums[i]==num1)cnt1++;
else if(nums[i]==num2)cnt2++;
else if(cnt1==0){num1=nums[i];cnt1=1;}
else if(cnt2==0){num2=nums[i];cnt2=1;}
else{
cnt1--;
cnt2--;
}
}
int c1=0,c2=0;
for(int i=0; i<nums.size(); i++){
if(nums[i]==num1)c1++;
if(nums[i]==num2)c2++;
}
if(c1>n)ans.push_back(num1);
if(c2>n && num1!=num2)ans.push_back(num2);
return ans;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.