# Majority Element，Moore's Voting

### 遍历一次，保存一个长度为k - 1的数组：

* **如果数组中包括这个数，则该数count + 1**
* **如果数组中有空位，则放入概该，count置为1**
* **如果数组中有数字count为0，则替换该数，count置为1**
* **所有数字count减1**

### 最后数组中剩下的数，就是candidate，每个统计一下就可以了

### 这个方法可以解决任意1/k的majority number

## [Majority Element](https://leetcode.com/problems/majority-element/)

经典的投票算法。

```java
public class Solution {
    public int majorityElement(int[] num) {

        int major=num[0], count = 1;
        for(int i=1; i<num.length;i++){
            if(count==0){
                count++;
                major=num[i];
            }else if(major==num[i]){
                count++;
            }else count--;

        }
        return major;
    }
}
```

## [Majority Element II](https://leetcode.com/problems/majority-element-ii/)

### Moore's Voting Algorithm.

遍历一次，保存一个长度为k - 1的数组： 1. 如果数组中包括这个数，则该数count + 1 2. 如果数组中有空位，则放入该数，count置为1 3. 如果数组中有数字count为0，则替换该数，count置为1 4. 所有数字count减1

最后数组中剩下的数，就是candidate; 此时再扫一遍数组，确认每个 candidate 的真正出现次数，并根据时候符合最终要求添加到最终结果里。

在这个算法中，count = 0 并不一定代表这个数不是 majority 应该被“立刻”踢出去。

这个方法可以解决任意n/k的majority number

从思想上说，这种做法有点像蓄水池抽样，又有点像 find the celebrity，都是 streaming data 然后维护固定 size 进行淘汰的机制。

```java
public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        if(nums == null || nums.length == 0) return list;

        int count1 = 0;
        int count2 = 0;
        int num1 = 0;
        int num2 = 1; 
        // 1 and 2 should be initialized to be different numbers

        for(int i = 0; i < nums.length; i++){
            if(nums[i] == num1){
                count1++;
            } else if(nums[i] == num2) {
                count2++;
            } else if(count1 == 0){
                num1 = nums[i];
                count1 = 1;
            } else if(count2 == 0){
                num2 = nums[i];
                count2 = 1;
            } else {
                count1 --;
                count2 --;
            }
        }
        int n = nums.length;

        count1 = 0;
        count2 = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == num1) count1++;
            else if(nums[i] == num2) count2++;
        }

        if(count1 > n / 3) list.add(num1);
        if(count2 > n / 3) list.add(num2);

        return list;
    }
}
```

## [Majority Number III](http://www.lintcode.com/en/problem/majority-number-iii/)

同样的思路扩展开来的通用解法，不过注意这题说了只会有一个 majority element 所以最后 return 那里有所不同，但是这个算法完全可以找到所有 k - 1 个。

```java
    public int majorityNumber(ArrayList<Integer> nums, int k) {
        // write your code
        int n = nums.size();

        List<Integer> numList = new ArrayList<>();
        List<Integer> countList = new ArrayList<>();

        if(nums == null || nums.size() == 0) return -1;

        for(int i = 0; i < n; i++){
            int num = nums.get(i);
            if(numList.size() < k - 1 && !numList.contains(num)){
                numList.add(num);
                countList.add(1);
            } else {
                int index = numList.indexOf(num);
                if(index != -1){
                    // current number is in candidate list;
                    countList.set(index, countList.get(index) + 1);
                } else {
                    int zeroIndex = countList.indexOf(0);
                    if(zeroIndex != -1){
                        numList.remove(zeroIndex);
                        countList.remove(zeroIndex);
                        numList.add(num);
                        countList.add(1);
                    } else {
                        for(int j = 0; j < countList.size(); j++){
                            countList.set(j, countList.get(j) - 1);
                        }
                    }
                }
            }
        }

        //List<Integer> rst = new ArrayList<>();
        for(int i = 0; i < numList.size(); i++){
            int count = 0;
            for(int num : nums){
                if(num == numList.get(i)) count++;
            }
            //if(count > n / k) rst.add(numList.get(i));
            if(count > n / k) return numList.get(i);
        }
        return -1;
    }
```

## (Google) Majority Element

<http://www.1point3acres.com/bbs/thread-191900-1-1.html>

之前google面经里有的关于majority element的题，就是一个排序数组有n个值，求所有出现次数等于或者超过n / k的值。 比如\[1 1 2 2 2 2 3 4 5 5 5 5] k = 3 return \[2,5]

### 解决办法就是依次检查所有可能的出现 majority element 的位置 \[n/k,2n/k, .... ,n] ，在每个位置上根据当前元素做 search for range，O(log n)，如此重复最多 k 次即可。


---

# 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://mnunknown.gitbook.io/algorithm-notes/majority_element.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.