majority element(Moore’s Voting Algorithm)

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);
                }
            }
        }
    }
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

原文链接：majority element(Moore’s Voting Algorithm)