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) formulafindcount(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);}}}}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); } } } }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); } } } }
Enter fullscreen mode Exit fullscreen mode
Output:5 Majority Element count =6
暂无评论内容