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)

© 版权声明
THE END
喜欢就支持一下吧
点赞8 分享
Seeing your adorable smile is the absolute best part of my day.
看见你可爱的笑容绝对是我一天中最美好的事
评论 抢沙发

请登录后发表评论

    暂无评论内容