8. Majority Element

Topic :

arrays

Difficulty :

easy

Problem Link :

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 1:

Input: nums = [3,2,3]
Output: 3
Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

solution

import java.io.*;
import java.util.*;
class Majority_Element_I
{  static int MajorityEle(int []arr)
    { int ansIndex=0;
        int count=0;
        for(int i=0;i<arr.length;i++)
        { if( arr[ansIndex]==arr[i])
                count++;
            else 
                count--;

            if(count==0)
            { ansIndex=i;
                count=1;
            }
        }

        int freq=0;
        for(int i=0;i<arr.length;i++)
        { if (arr[i]==arr[ansIndex])
                freq++;
        }

        if(freq>arr.length/2)
            return arr[ansIndex];
        else 
            return -99999;
    }

    public static void main(String args[])
    { int arr[]={2,2,1,1,1,2,2};
        System.out.println(MajorityEle(arr));
    }
}