LintCode

Majority Number

Michael

Sep 4, 2016

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) extra space

This problem could be solved using Boyer–Moore majority vote algorithm.

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    public int majorityNumber(ArrayList<Integer> nums) {
        if (nums == null || nums.size() == 0) {
            return -1;
        }
        
        int candidate = 0, counter = 0;
        
        for (int i : nums) {
            if (counter == 0) {
                candidate = i;
                counter = 1;
            } else if (i == candidate) {
                counter++;
            } else if (i != candidate) {
                counter--;
            }
        }
        
        return candidate;
    }
}

Hope this helps,
Michael