Given an array arr. Find the majority element in the array. If no majority exists, return -1. A majority element in an array is an element that appears strictly more than arr.size() / 2 times in the array.
Examples :
Input : arr[] = {1, 1, 2, 1, 3, 5, 1}
Output : 1
Explanation: Note that 1 appear 4 times which is more than 7 / 2 times
Input : arr[] = {3, 3, 4, 2, 4, 4, 2, 4}
Output : -1
Explanation: There is no element whose frequency is greater than the half of the size of the array size.
Input : arr[] = {3}
Output : 3
Explanation: Appears more than n/2 times
Find the majority element (element appearing more than n/2 times) – Moore’s Voting Algorithm
package afterfeb13;
public class MajorityElement {
public static void main(String[] args) {
int[] arr = { 3, 5, 3, 3, 3, 3, 5, 5, 5, 5, 5 };
int form = arr.length / 2;// (n/2) formula
findcount(arr, form);
}
private static void findcount(int[] arr, int form) {
for (int j = 0; j < arr.length; j++) {
int key = arr[j];
int count = 1;
for (int i = j + 1; i < arr.length; i++)
{
if (key == arr[i]) {
arr[i] = '*';
count++;
}
}
if (key != '*') {
if (count > form) {
System.out.println(key + " Majority Element count =" + count);
}
}
}
}
Output:5 Majority Element count =6
Top comments (0)