本文主要是介绍leetcode 229. 求众数 II (摩尔投票法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
示例 1:
输入: [3,2,3]
输出: [3]示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]解题思路：
摩尔投票法：
摩尔投票算法的时间和空间都很低，时间复杂度为O(n)，空间复杂度为O(1)，可以快速的计算出一个数组中出现次数过半的数即大多数（majority），算法核心思想是同加，异减。算法会保存一个当前大多数，和得分，当遇到一个数不是当前大多数时，得分会减一，当减到0时，大多数会发生改变，并且重置得分为1。
这里需要区分的是，摩尔算法不能用来得到众数（mode），例如数组：[1,1,1,2,2,3,3,4,4]，摩尔算法得出最后的结果应该是4，但4并不是众数，可是显然4也不是大多数，那是因为，大多数是指出现次数过半的数，而这个数组中没有这样的数，所以摩尔算法是失效的，对于这种情况采取需要重新投票。
算法伪代码：
初始化元素 major = 0， count = 0
遍历数组中每一个元素x：if count == 0major = xcount = 1else if major == x++countelse --count
return majorleetcode 229 解题：
每次删除三个不相同的数，最后留下的一定是出现次数超过1/3的数，这个思想可以推广到出现次数超过1/k次的元素有哪些。
- 因为出现次数大于n/3的元素最多只有两个，所以最开始可以维护两个数字(num1,num2)和两个计数器(counter1,counter2)；
- 遍历数组，当数组中元素和num1或者num2相同，对应的counter1或者counter2加1；
- 如果counter1或counter2为0，将遍历到的该元素赋给num1或者nums2；
- 否则counter1和counter2都减1。
代码：
class Solution {
public:vector<int> majorityElement(vector<int>& nums) {vector<int> res;int value1 = INT_MIN, value2 = INT_MIN, count1 = 0, count2 = 0;for(auto i : nums){if(i == value1)++count1;else if(i == value2)++count2;else if(count1 == 0){value1 = i;count1 = 1;}else if(count2 == 0){value2 = i;count2 = 1;}else{--count1;--count2;}}int counter1 = 0, counter2 = 0;for(auto i : nums){ //第二遍遍历来确定value1与value2是否大于 n/3if(i == value1)++counter1;else if(i == value2)++counter2;}if(counter1 > nums.size() / 3)res.push_back(value1);if(counter2 > nums.size() / 3)res.push_back(value2);return res;}
};
这篇关于leetcode 229. 求众数 II (摩尔投票法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
