# 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](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_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](http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html)

> 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

```java
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](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm)

```java
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;
    }
}
```