Majority Element

• LeetCode: Majority Element

• 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.

• Analysis:

This problem fits "Boyer–Moore majority vote algorithm".

From problem description, the majority element appears more than ⌊ n/2 ⌋ times.

We assume a box store the majority at the current situation.

1. push nums[i] into the box, if the box is empty or equal to the number in the box.

2. pop the number from the box, if nums[i] isn't equal to the number in the box.

• Code - Java:

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (count == 0) { // select one as majority
                count++;
                candidate = nums[i];
            } else if (candidate == nums[i]) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}

• Code - C++:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int candidate = 0;
        int len = nums.size();
        for (int i = 0; i < len; i++) {
            if (count == 0) { // select one as majority
                count++;
                candidate = nums[i];
            } else if (candidate == nums[i]) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
};

• Code - Python:

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count, candidate = 0, 0
        for num in nums:
            if count == 0:
                count += 1
                candidate = num
            elif candidate == num:
                count += 1
            else:
                count -= 1
        return candidate

• Code - C:

int majorityElement(int* nums, int numsSize) {
    int count = 0;
    int candidate = 0;
    for (int i = 0; i < numsSize; i++) {
        if (count == 0) { // select one as majority
            count++;
            candidate = nums[i];
        } else if (candidate == nums[i]) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}

• Time Complexity: O(N), N is the length of input array

• Space Complexity: O(1)