Finding the majority Element with Moore’s Voting Algorithm

Leetcode problem:

https://leetcode.com/problems/majority-element/description/

Problem Description:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exists in the array.

Algorithm Link:

https://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

moores-voting-algorithm

Solution:


public class Main {

    public static int majorityElement(int[] nums) {

        int currentElement = 0;
        int counter = 0;
        for (int num : nums) {
            if (counter == 0) {
                currentElement = num;
                counter = 1;
            }
            else {
                if (num == currentElement) {
                    counter++;
                }
                else {
                    counter--;
                }
            }
        }
        return currentElement;
    }

    public static void main(String[] args) {

        int[] nums = new int[] { 1, 3, 4, 5, 5, 1, 1 };
        System.out.println(majorityElement(nums));
    }
}


Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s