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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/high_frequency/majority_number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.