Skip to content

169 Majority Element – Easy

Problem:

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 exist in the array.

Thoughts:

Use a counter for currently met element. Since the major element will eventually win no matter where it starts.

Solutions:

public class Solution {
    public int majorityElement(int[] num) {
        int candidate = num[0];
        int counter = 1;
        for (int i = 1; i < num.length; i ++){
            if (counter == 0){
                candidate = num[i];
                counter = 1;
            }
            else{
                if (num[i] == candidate)
                    counter ++;
                else
                    counter --;
            }
        }//for i
        return candidate;
    }
}