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.
分析：和Majority Number类似的思路。但是要考虑不存在的情况。时间复杂度O(n),空间复杂度O(1)
class Solution { public: vector<int> majorityElement(vector<int>& nums) { vector<int> res; if (nums.empty()) return res; if (nums.size() == 1) { res.push_back(nums[0]); return res; } int candidate1 = 0; int candidate2 = 0; int times1 = 0; int times2 = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] == candidate1) { times1++; } else if (nums[i] == candidate2) { times2++; } else if (times1 == 0) { times1 = 1; candidate1 = nums[i]; } else if (times2 == 0) { times2 = 1; candidate2 = nums[i]; } else { times1--; times2--; } } times1 = 0; times2 = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] == candidate1) { times1++; } else if (nums[i] == candidate2) { times2++; } } if (times1 > nums.size() / 3) res.push_back(candidate1); if (times2 > nums.size() / 3) res.push_back(candidate2); return res; } };
[LeetCode] Majority Element II
原文：http://www.cnblogs.com/vincently/p/4823662.html