Find Majority Element in an Array : Occurrence more than n/2

import java.util.Scanner;
//Method 1
/*The basic solution is to have two loops and keep track of maximum count for all different elements. If maximum count becomes greater than n/2 then break
the loops and return the element having maximum count. If maximum count doesn’t become more than n/2 then majority element doesn’t exist.
Time Complexity: O(n*n).
Auxiliary Space : O(1)

//Method 2
Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.
The method works well for the cases where n/2+1 occurrences of the majority element is present in the starting of the array, for example {1, 1, 1, 1, 1, 2, 3, 4}.

Time Complexity: If a binary search tree is used then time complexity will be O(n^2). If a self-balancing-binary-search tree is used then O(nlogn)
Auxiliary Space: O(n)


//Method 3  Moore’s Voting Algorithm
This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.
1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s 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.

*/

public class FindMajority {
private static int findMajority(int[] array){
int majorityCand = array[0];
int count = 0;
for(int i = 0; i< array.length; i++){
if(array[i] == majorityCand) count++;
else count--;
if(count == 0){
majorityCand = array[i];
count = 1;
}
}
count = 0;
for(int i = 0; i< array.length; i++){
if(array[i] == majorityCand) count++;
}
if(count > array.length/2) System.out.println("Majoirty element :" + majorityCand);
else System.out.println("No majority element !!");
return 0;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] array = new int[N];
for(int i = 0; i< N; i++){
array[i] = in.nextInt();
}
findMajority(array);
}
}