com.sl.algorithms.search.majorityelement

Class BoyerMooreVoting<T extends java.lang.Comparable>

java.lang.Object

com.sl.algorithms.search.majorityelement.BoyerMooreVoting<T>

All Implemented Interfaces:

BaseInterface<T>, Constants, MajorityFinder<T>

public class BoyerMooreVoting<T extends java.lang.Comparable>
extends java.lang.Object
implements MajorityFinder<T>

Boyer Moore Voting Algorithm

Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

Majority = n/2

Field Summary

Fields inherited from interface com.sl.algorithms.core.interfaces.base.Constants

ARRAY_IS_EMPTY, DATA_TYPE_NOT_SUPPORTED_YET, DECIMAL_RADIX, DELIMITER_COMMA, ELEMENT_NOT_FOUND, LIST_IS_EMPTY, OPERATION_NOT_SUPPORTED_YET

Constructor Summary

Constructors

Constructor and Description
BoyerMooreVoting()

Method Summary

Modifier and Type	Method and Description
T	findMajorityElement(T[] candidates)
boolean	isMajority(T[] candidates, T majorityElement)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.sl.algorithms.core.interfaces.base.BaseInterface

checkArray, checkIntArray, checkList

Constructor Detail

BoyerMooreVoting

public BoyerMooreVoting()

Method Detail

findMajorityElement

public T findMajorityElement(T[] candidates)

Specified by:

findMajorityElement in interface MajorityFinder<T extends java.lang.Comparable>

isMajority

public boolean isMajority(T[] candidates,
                          T majorityElement)

Specified by:

isMajority in interface MajorityFinder<T extends java.lang.Comparable>