What is majority element in integer array?
- Given an integer elements, find the majority element in an array.
- We will find majority element using Boyer–Moore majority vote algorithm.
- The elements which exists more the half of elements in an array is a majority element in an array..
Examples: find majority element in integer array (java)
Example 1:
- Given an array { 21, 23, 21, 23, 21 } of length 5.
- Majority elements should exists more than half.
- Occurrence of majority elements should be more 5/2 i.e. 2.
- In an array 21 appears 3 times, 23 & 24 appears only once.
- Clearly 21 exists more than half of elements in an array.
- Element 21 is a majority element.
Example 2:
- Given an array { 41, 42, 43, 41 } of length 4.
- Majority elements should exists more than half.
- Occurrence of majority elements should be more 4/2 i.e. 2.
- In an array 41 appears 2 times & 42,43 appears only once.
- No element occurs more than 2.
- There is no majority element exists in an array.
Boyer – Moore majority vote algorithm:
- Boyer Moore voting algorithm is based upon cancelling technique.
- Declare the counter and candidate element.
- Iterate through the elements of array.
- If counter is zero
- Note down the candidate element & increment the counter
- If counter is not equal to zero
- If current element in iteration is same as candidate element
- increment the counter
- else decrements the counter
- If current element in iteration is same as candidate element
- If counter is zero
- end of iteration.
- If counter is zero, then there is no majority element in array.
- Now, check whether candidate element is a majority element.
- Candidate element should occurs more than n/2 times.
- If yes, we found the majority element.
- Time complexity of algorithm is O (n)
Program: Majority element in integer array – Boyer Moore Algorithm (Java)
package org.learn.arrays; import java.util.Arrays; public class BoyerMooreMajorityElements { public static void main(String[] args) { int elements[] = { 41 , 42 , 43 , 41 }; int element = majorityElement(elements); String arrString = Arrays.toString(elements); if (element > - 1 ) { System.out.printf( "1. Majority element in an array %s is: %d" , arrString, element); } else { System.out.printf( "1. No majority element found in an array : %s" , arrString); } elements = new int [] { 21 , 23 , 21 , 23 , 21 }; element = majorityElement(elements); arrString = Arrays.toString(elements); if (element > - 1 ) { System.out.printf( "\n2. Majority element in an array %s is: %d" , arrString, element); } else { System.out.printf( "\n2. No majority element found in an array : %s" , arrString); } } private static int majorityElement( int [] arr) { int element = - 1 ; int counter = 0 ; int length = arr.length; int index = 0 ; while (index < length) { if (counter == 0 ) { element = arr[index]; counter++; } else if (element == arr[index]) { counter++; } else { counter--; } index++; } if (counter == 0 ) { // No majority element found return - 1 ; } index = - 1 ; counter = 0 ; while (++index < length) { if (element == arr[index]) { counter++; } } if (counter > length / 2 ) return element; return - 1 ; } } |
Output: majority element using Boyer–Moore vote algorithm in java
1. No majority element found in an array [41, 42, 43, 41] 2. Majority element in an array [21, 23, 21, 23, 21] is: 21 |