本文主要是介绍229.Majority Element II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
Hint:
- How many majority elements could it possibly have?Show More Hint
这道题让我们求出现次数大于n/3的众数，而且限定了时间和空间复杂度，那么就不能排序，也不能使用哈希表，这么苛刻的限制条件只有一种方法能解了，那就是摩尔投票法 Moore Voting，这种方法在之前那道题Majority Element 求众数中也使用了。题目中给了一条很重要的提示，让我们先考虑可能会有多少个众数，经过举了很多例子分析得出，任意一个数组出现次数大于n/3的众数最多有两个，具体的证明我就不会了，我也不是数学专业的。那么有了这个信息，我们使用投票法的核心是找出两个候选众数进行投票，需要两遍遍历，第一遍历找出两个候选众数，第二遍遍历重新投票验证这两个候选众数是否为众数即可，选候选众数方法和前面那篇Majority Element 求众数一样，由于之前那题题目中限定了一定会有众数存在，故而省略了验证候选众数的步骤，这道题却没有这种限定，即满足要求的众数可能不存在，所以要有验证。
class Solution {
public:vector<int> majorityElement(vector<int>& nums) {vector<int> res;int m = 0, n = 0, cm = 0, cn = 0;for (auto a : nums) {if (a == m) ++cm;else if (a ==n) ++cn;else if (cm == 0) m = a, cm = 1;else if (cn == 0) n = a, cn = 1;else --cm, --cn;}cm = cn = 0;for (auto a : nums) {if (a == m) ++cm;else if (a == n) ++cn;}if (cm > nums.size() / 3) res.push_back(m);if (cn > nums.size() / 3) res.push_back(n);return res;}
};这篇关于229.Majority Element II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
