# 0229. 求众数 II

### 题目地址(229. 求众数 II)

<https://leetcode-cn.com/problems/majority-element-ii/>

### 题目描述

```
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

 

示例 1：

输入：[3,2,3]
输出：[3]
示例 2：

输入：nums = [1]
输出：[1]
示例 3：

输入：[1,1,1,3,3,2,2,2]
输出：[1,2]
 

提示：

1 <= nums.length <= 5 * 104
-10^9 <= nums[i] <= 10^9

```

### 前置知识

* 摩尔投票法

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

这道题目和[169.majority-element](/leetcode-solution/easy/169.majority-element.md) 很像。

我们仍然可以采取同样的方法 - “摩尔投票法”， 具体的思路可以参考上面的题目。

但是这里有一个不同的是这里的众数不再是超过`1 / 2`,而是超过`1 / 3`。题目也说明了，超过三分之一的有可能有多个

> 实际上就是 0，1，2 三种可能。

因此我们不能只用一个 counter 来解决了。 我们的思路是同时使用两个 counter，其他思路和上一道题目一样。

最后需要注意的是这两个 counter 只是出现次数最多的两个数字, 不一定都满足条件出现次数大于 1/3，因此最后我们需要进行过滤筛选。

这里画了一个图，大家可以感受一下：

![229.majority-element-ii-1](https://p.ipic.vip/geonsr.jpg)

![229.majority-element-ii-1](https://p.ipic.vip/cf2r6u.jpg)

### 关键点解析

* 摩尔投票法
* 两个 counter
* 最后得到的只是出现次数最多的两个数字，有可能不满足出现次数大于 1/3

### 代码

代码支持：CPP，JS, Java, Python

CPP Code:

```cpp
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int c1 = 0, c2 = 0, v1 = 0, v2 = 1;
        for (int n : nums) {
            if (v1 == n) ++c1;
            else if (v2 == n) ++c2;
            else if (!c1) v1 = n, ++c1;
            else if (!c2) v2 = n, ++c2;
            else --c1, --c2;
        }
        c1 = c2 = 0;
        for (int n : nums) {
            if (v1 == n) ++c1;
            if (v2 == n) ++c2;
        }
        vector<int> v;
        if (c1 > nums.size() / 3) v.push_back(v1);
        if (c2 > nums.size() / 3) v.push_back(v2);
        return v;
    }
};
```

JS Code：

```js
/*
 * @lc app=leetcode id=229 lang=javascript
 *
 * [229] Majority Element II
 */
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function (nums) {
  const res = [];
  const len = nums.length;
  let n1 = null,
    n2 = null,
    cnt1 = 0,
    cnt2 = 0;

  for (let i = 0; i < len; i++) {
    if (n1 === nums[i]) {
      cnt1++;
    } else if (n2 === nums[i]) {
      cnt2++;
    } else if (cnt1 === 0) {
      n1 = nums[i];
      cnt1++;
    } else if (cnt2 === 0) {
      n2 = nums[i];
      cnt2++;
    } else {
      cnt1--;
      cnt2--;
    }
  }

  cnt1 = 0;
  cnt2 = 0;

  for (let i = 0; i < len; i++) {
    if (n1 === nums[i]) {
      cnt1++;
    } else if (n2 === nums[i]) {
      cnt2++;
    }
  }

  if (cnt1 > (len / 3) >>> 0) {
    res.push(n1);
  }
  if (cnt2 > (len / 3) >>> 0) {
    res.push(n2);
  }

  return res;
};
```

Java Code：

```java
/*
 * @lc app=leetcode id=229 lang=java
 *
 * [229] Majority Element II
 */
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0)
            return res;
        int n1 = nums[0], n2 = nums[0], cnt1 = 0, cnt2 = 0, len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] == n1)
                cnt1++;
            else if (nums[i] == n2)
                cnt2++;
            else if (cnt1 == 0) {
                n1 = nums[i];
                cnt1 = 1;
            } else if (cnt2 == 0) {
                n2 = nums[i];
                cnt2 = 1;
            } else {
                cnt1--;
                cnt2--;
            }
        }
        cnt1 = 0;
        cnt2 = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] == n1)
                cnt1++;
            else if (nums[i] == n2)
                cnt2++;
        }
        if (cnt1 > len / 3)
            res.add(n1);
        if (cnt2 > len / 3 && n1 != n2)
            res.add(n2);
        return res;
    }
}

```

Python Code:

```py

class Solution:
    def majorityElement(self, nums):
        c1 = c2 = 0
        v1 = v2 = -1

        for num in nums:
            if num == v1: c1 += 1
            elif num == v2: c2 += 1
            elif c1 == 0:
                c1 = 1
                v1 = num
            elif c2 == 0:
                c2 = 1
                v2 = num
            else:
                c1 -= 1
                c2 -= 1
        # check
        c1 = c2 = 0
        for num in nums:
            if v1 == num: c1 += 1
            if v2 == num: c2 += 1
        ans = []
        if c1 > len(nums)//3: ans.append(v1)
        if c2 > len(nums)//3: ans.append(v2)
        return list(set(ans))
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$

### 扩展

如果题目中 3 变成了 k，怎么解决？

大家可以自己思考一下，我这里给一个参考链接：<https://leetcode.com/problems/majority-element-ii/discuss/63500/JAVA-Easy-Version-To-Understand!!!!!!!!!!!!/64925>

这个实现说实话不是很好，大家可以优化一下。

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/zr18ww.jpg)


---

# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/229.majority-element-ii.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.