This content originally appeared on DEV Community and was authored by sachin26
Problem Statement :-
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
Input : nums = [2,2,1,1,1,2,2]
Result : 2
Solution 1
using sorting,we can easily find the majority element in an array.
lets understand this approach step by step.
step-1 sort the array nums.
stpe-2 initialize three variables max = 0, count = 1, majEle = 0 .
step-3 run a loop from i=1 to n-1.
1. increase counting if the adjacent elements are the same..
ifnums[i] == nums[i+1]thencount++2. if not
nums[i] == nums[i+1], start recounting for new majority element.3. if
count > maxthen re-assign newmax&majEle
Java
class Solution {
public int majorityElement(int[] nums) {
if(nums.length == 1) return nums[0];
Arrays.sort(nums);
int max =0;
int majEle = 0;
int count = 1;
for(int i=0; i< nums.length-1; i++){
if(nums[i] == nums[i+1]){
count++;
}else{
count = 1;
}
if(count > max) {
max = count ;
majEle = nums[i];
}
}
return majEle;
}
}
Time Complexity : O(nlogn) + O(n)
Space Complexity : O(1)
Solution 2
by using Boyer–Moore majority vote algorithm, we can solve this problem in O(n) time complexity
in this algorithm, we increase or decrease the count of the majority element, in the last, we will get our majority element.
step-1 initialise two variables majEle = nums[0], count = 1
step-2 run a loop from i=1 to n, then
1. if we found the
majEle, increase thecountby1
2. if notmajEle, decrease thecountby1
3. if count become0then, re-initialsemajEle&count
Java
class Solution {
public int majorityElement(int[] nums) {
int majEle = nums[0];
int count = 1;
for(int i=1; i<nums.length; i++){
if(count == 0){
majEle = nums[i];
count++;
}else if(nums[i] == majEle){
count++;
}else{
count--;
}
}
return majEle;
}
}
Thank you for reading this article. save it for future use.
if you found something, let me in the comment section.
This content originally appeared on DEV Community and was authored by sachin26
sachin26 | Sciencx (2022-01-17T09:34:46+00:00) Striver’s SDE Sheet Journey – #15 Majority Element (>N/2 times). Retrieved from https://www.scien.cx/2022/01/17/strivers-sde-sheet-journey-15-majority-element-n-2-times/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.