Site icon

Majority element in integer array (Boyer Moore’s voting algorithm) in java

What is majority element in integer array?

Examples: find majority element in integer array (java)

Example 1:

Example 2:

Boyer – Moore majority vote algorithm:

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
Exit mobile version