Majority Number

Question

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

Analysis

最直观的想法就是，建立HashMap，记录list中的每一个integer元素的个数，如果大于1/2 list长度，即可返回。

进一步分析发现，其实并不需要记录所有的integer元素的个数，可以只记录当前最多的那一个majority。这种方法也称为 wikipedia: Boyer–Moore majority vote algorithm

The Boyer-Moore Vote Algorithm solves the majority vote problem in linear time O(n) and logarithmic space O(log n)

Moore's Page

As we sweep we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.

When we move the pointer forward over an element e:

• If the counter is 0, we set the current candidate to e and we set the counter to 1.

• If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.

When we are done, the current candidate is the majority element, if there is a majority.

换一种角度，是否可以直接从list中读取这个majority呢？如果对list进行排序，那么1/2处的元素，也就是majority的那个integer了。当然这种方法有个问题，就是对于没有majority的情况下（没有一个达到了1/2 总长度），是无法判断是否存在majority的，如果题目中明确一定存在这样的majority，那么这种方法也是可行的。

时间 O(n), 空间 O(1)

Solution

HashMap Solution

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 0;
        }

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int listSize = nums.size();
        int halfSize = listSize / 2;
        int result = 0;

        for (int i = 0; i < listSize; i++) {
            int num = nums.get(i);

            if (!map.containsKey(num)) {
                map.put(num, 1);
            } else {
                map.put(num, 1 + map.get(num));
            }

            if (map.get(num) > halfSize) {
                result = num;
            }
        }

        return result;
    }
}

Boyer–Moore majority vote algorithm

public class Solution {
    /**
     * @param nums: a array of integers
     * @return: find a majority element
     */
    public int majorityElement(int[] nums) {
        int n = nums.length;
        int candidate = nums[0], counter = 0;
        for (int i : nums) {
            if (counter == 0) {
                candidate = i;
                counter = 1;
            } else if (candidate == i) {
                counter++;
            } else {
                counter--;
            }
        }

        counter = 0;
        for (int i : nums) {
            if (i == candidate) counter++;
        }
        if (counter < (n + 1) / 2) return -1;
        return candidate;
    }
}