May 06, 2020

#LeetCode:Majority Element

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

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 CHECKOther LeetCode Solutions in Java

-K Himaanshu Shuklaa..

No comments:

Post a Comment