#LeetCode:Majority Element

Also Check: Solutions Of May LeetCoding Challenge (2020)

Given an array of size n, find the majority element. The majority element is the element that appears more than n/2 times. You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:
Input: [3,2,3]
Output: 3

Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2

GIT URL: Java Solution of Leet Code's Majority Element problem

Java Solution 1: Using HashMap

Java Solution 2: Using Boyer–Moore majority vote algorithm
Algorithm:
1). In this algorithm, we will process each element of the array. We will maintain a counter (which is initialized with 0), now let's say the current element is x.
2). We will check if the counter is 0, if yes then set the current candidate to x and increment the counter.
3). Else, we need to increment or decrement the counter after checking whether x is equal to the current candidate or not..
4). After iteration, if the sequence has a majority it will be x.

NOTE: The Boyer–Moore majority vote algorithm produces correct results only when majority element is present in the input.

Pseudocode:
Initialize an element majorityElement to -1 and counter = 0

for each element x of the input sequence:
    if counter = 0, then
        assign majorityElement = x and increment the counter
    else
        if majorityElement = x, then increment the counter
    else
       decrement the counter

return majorityElement

ALSO CHECK: Other LeetCode Solutions in Java

-K Himaanshu Shuklaa..