Boyer-Moore majority vote algorithm(摩爾投票算法)
簡介
Boyer-Moore majority vote algorithm(摩爾投票算法)是一種在線性時間O(n)和空間復(fù)雜度的情況下，在一個元素序列中查找包含最多的元素趟径。它是以Robert S.Boyer和J Strother Moore命名的，1981年發(fā)明的查蓉，是一種典型的流算法(streaming algorithm)。
在它最簡單的形式就是榜贴，查找最多的元素豌研，也就是在輸入中重復(fù)出現(xiàn)超過一半以上(n/2)的元素妹田。如果序列中沒有最多的元素，算法不能檢測到正確結(jié)果鹃共，將輸出其中的一個元素之一鬼佣。
當(dāng)元素重復(fù)的次數(shù)比較小的時候，對于流算法不能在小于線性空間的情況下查找頻率最高的元素霜浴。
算法描述
算法在局部變量中定義一個序列元素(m)和一個計數(shù)器(i)晶衷，初始化的情況下計數(shù)器為0. 算法依次掃描序列中的元素，當(dāng)處理元素x的時候阴孟，如果計數(shù)器為0晌纫，那么將x賦值給m，然后將計數(shù)器(i)設(shè)置為1永丝，如果計數(shù)器不為0锹漱，那么將序列元素m和x比較，如果相等慕嚷，那么計數(shù)器加1哥牍，如果不等，那么計數(shù)器減1喝检。處理之后嗅辣，最后存儲的序列元素(m)，就是這個序列中最多的元素挠说。
如果不確定是否存儲的元素m是最多的元素澡谭，還可以進(jìn)行第二遍掃描判斷是否為最多的元素。
perudocode
- Initialize an element m and a counter i with i = 0
- For each element x of the input sequence:
- if i = 0, then assign m = x and i = 1
- else if m = x, then assign i = i + 1
- else assign i = i ? 1
- Return m
算法舉例
Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.
You may assume that the array is non-empty and the majority element always exist in the array.
實現(xiàn)代碼
class Solution {
public:
// moore majority vote algorithm
int majorityElement(vector<int>& nums) {
int m;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
if (count == 0) {
m = nums[i];
count++;
} else if (nums[i] == m) {
count++;
} else
count--;
}
return m;
}
};
