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 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..
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 CHECK: Other LeetCode Solutions in Java
-K Himaanshu Shuklaa..
No comments:
Post a Comment