Class MajoritarianElement

java.lang.Object
topics.divideconquer.MajoritarianElement
public class MajoritarianElement extends Object
//DIVIDE AND CONQUER PROBLEM: IS THERE A MAJORITARIAN ELEMENT IN n ELEMENTS?
Author:
vicegd

  • Constructor Summary

    Constructors
    Constructor
    Description
    MajoritarianElement()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    majoritarian1(int[] v)
    This method iteratively calculates whether there is or not majority element.
    boolean
    majoritarian2(int[] v)
    This method previously orders the vector O(nlogn) and then it looks for the majoritarian element (if there is one), knowing that if there is one, it should be in the central position (among others) v[n/2].
    boolean
    majoritarian3(int[] v)
    This method is recursive and difficult to understand.

    Methods inherited from class Object

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

  • Constructor Details

    • MajoritarianElement

      public MajoritarianElement()

  • Method Details

    • majoritarian1

      public boolean majoritarian1(int[] v)
      This method iteratively calculates whether there is or not majority element. It is quadratic O(n^2)
      Parameters:
      v - Array with numbers to be used for the calculation
      Returns:
      Whether there is a majoritarian element

    • majoritarian2

      public boolean majoritarian2(int[] v)
      This method previously orders the vector O(nlogn) and then it looks for the majoritarian element (if there is one), knowing that if there is one, it should be in the central position (among others) v[n/2]. It is O(nlogn) + O(n) - O(nlogn)
      Parameters:
      v - Array with numbers to be used for the calculation
      Returns:
      Whether there is a majoritarian element

    • majoritarian3

      public boolean majoritarian3(int[] v)
      This method is recursive and difficult to understand. It is explained in the base book (section 3.11) and has a linear complexity O(n). It is DandV by division with a=1,b=2,k=1 - O(n)
      Parameters:
      v - Array with numbers to be used for the calculation
      Returns:
      Whether there is a majoritarian element