LeetCode之Majority Element II

本文主要是介绍LeetCode之Majority Element II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*O(n)解法。此题与Majority Element类似，考查摩尔投票的知识迁移。
由于每个Majority Element的都more than⌊ n/3 ⌋，那么一个数组中顶多有两个
Majority Elements。因此，可以先确定这个两个可能的元素，由于可能存在0个，1个，
2个Majority Element，所以需要在确定这两个元素后进行检查。
参考自：http://www.cnblogs.com/grandyang/p/4606822.html*/
class Solution {
public:vector<int> majorityElement(vector<int>& nums) {int candidate0(0), candidate1(0), count0(0), count1(0);for(int i = 0; i < nums.size(); ++i){if(nums[i] == candidate0) ++count0;else if(nums[i] == candidate1) ++count1;else{if(count0 == 0){candidate0 = nums[i];count0 = 1; } else if(count1 == 0){candidate1 = nums[i]; count1 = 1;}else{--count0; --count1;}}}count0 = 0;count1 = 0;for(int i = 0; i < nums.size(); ++i){if(nums[i] == candidate0) ++count0;else if(nums[i] == candidate1) ++count1;}vector<int> res;if(count0 > nums.size()/3) res.push_back(candidate0);if(count1 > nums.size()/3) res.push_back(candidate1);return res;}
};

这篇关于LeetCode之Majority Element II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---