一. 題目描述
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?
二. 題目分析
題目大意是，給定一個大小為n的整數數組，從中找出所有出現次數超過 ? n/3 ? 的元素。要求算法滿足線性時間復雜度和O(1)的空間復雜度。
提示：一共可能有多少個majority elements？
首先應該意識到一點： 在一個數組中出現超過三分之一次的元素，這樣的元素最多只能有兩個，超過兩個就與命題相矛盾。該題與題目Majority Element的思路相類似，只是該題中最多可能出現兩個majority elements。在這裡，要求線性時間復雜度和O(1)的空間復雜度，唯有使用摩爾投票法的思想來解。
摩爾投票法的基本思想很簡單，在每一輪投票過程中，從數組中找出一對不同的元素，將其從數組中刪除。這樣不斷的刪除直到無法再進行投票，如果數組為空，則沒有任何元素出現的次數超過該數組長度的一半。如果只存在一種元素，那麼這個元素則可能為目標元素。
三. 示例代碼
// C++代碼
class Solution {
public:
vector majorityElement(vector& nums) {
vector result;
if (nums.size() == 0) return result;
int num1 = INT_MAX, num2 = INT_MAX;
int time1 = 0, time2 = 0;
for (int i = 0; i < nums.size(); ++i)
{
if (num1 == nums[i]) ++time1;
else if (num2 == nums[i]) ++time2;
else if (time1 == 0)
{
time1 = 1;
num1 = nums[i];
}
else if (time2 == 0)
{
time2 = 1;
num2 = nums[i];
}
else
{
--time1;
--time2;
}
}
time1 = 0, time2 = 0;
for (int i = 0; i < nums.size(); ++i)
{
if (num1 == nums[i]) ++time1;
else if (num2 == nums[i]) ++ time2;
}
if (time1 > nums.size() / 3) result.push_back(num1);
if (time2 > nums.size() / 3) result.push_back(num2);
return result;
}
};
// Python代碼
class Solution:
# param {integer[]} nums
# return integer[]
def majorityElement(self, nums):
if not nums:
return []
num1, num2, time1, time2 = None, None, 0, 0
for num in nums:
if num1 == num:
time1 += 1
elif num2 == num:
time2 += 1
elif time1 == 0:
num1, time1 = num, 1
elif time2 == 0:
num2, time2 = num, 1
else:
time1, time2 = time1 - 1, time2 - 1
numSize = len(nums)
return [n for n in (num1, num2) if
n is not None and nums.count(n) > numSize / 3]
四. 小結
關於摩爾投票法：http://mabusyao.iteye.com/blog/2223195
