多數投票算法(Majority Vote Algorithm)

假設有一個數組，其中含有N個非負元素，求其中是否存在一個元素其元素個數大於等於N/2。

分析：看到這個問題最先想到的是暴力算法，將數組在O(NlogN)的時間內進行排序，然後掃描一次數組就知道是否存在滿足條件的元素了。

算法實現：

int Majority_Vote_Sort(const int* a, const int n)
{
sort(a,n);
int count=0;
int max = 0;
int now = a[0];
int res = a[0];
for(int i=1; i<n; i++)
{
if(a[i] == now)
{
count++;
}
else
{
if(count > max)
{
max = count;
res = now;
}
now = a[i];
count = 0;
}
}
return max;
//return res;
}

上述算法可以在O(logN)的時間內找到滿足條件的元素，但是仔細觀察發現，算法中對數組的排序似乎是多余的，為此可以在算法排序處進行一定的改進便可以得到更加快速的算法。

學過hash表的同學看到這個問題通常容易想到使用一個定義一個數組count，其中數組的角標為原來數組的元素值，count數組的元素值代表了這個角標元素出現的次數，由此可以在掃面一遍數組的情況下獲得原數組中各個元素的個數，從而解決此題。也可以利用hash表來替代count數組，這樣做的話算法的魯棒性會更好。

算法實現

int Majority_Vote(const int* a, const int n)
{
int* res = new int[n];
for(int i=0; i<n; i++)
res[i] = 0;
for(int i=0; i<n; i++)
res[a[i]]++;
int max = res[0];
for(int i=1; i<n; i++)
{
if(max < res[i])
max = res[i];
}
delete[] res;
return max;
}

上述算法在時間復雜度上做到了最優，但是卻花費了額外的空間復雜度，為此，查閱文獻的時候發現了一個很神奇的方法A Fast Majority Vote Algorithm，此方法只需在常數空間復雜度上就可以實現上述算法的功能。

神奇算法的思路：（存在一個計數器count和一個臨時存儲當前元素的變量now）

1. 如果count==0，則將now的值設置為數組的當前元素，將count賦值為1；
2. 反之，如果now和現在數組元素值相同，則count++，反之count--；
3. 重復上述兩步，直到掃描完數組。
4. count賦值為0，再次從頭掃描數組，如果素組元素值與now的值相同則count++，直到掃描完數組為止。
5. 如果此時count的值大於等於n/2，則返回now的值，反之則返回-1；

算法實現

int Majority_Vote_update(const int* a, const int n)
{
struct item
{
int now;
int count;
};
item* t = new item;
t->count = 0;
for(int i=0; i<n; i++)
{
if(t->count == 0)
{
t->now = i;
t->count = 1;
}
else
{
if(t->now == a[i])
t->count++;
else
t->count--;
}
}
int res=0;
for(int i=0; i<n; i++)
{
if(t->now == a[i])
res++;
}
if(res >= n+1/2)
return res;
else
return -1;
}

上述算法只需在常數的額外空間的條件下就可以在常數的時間內判斷並找出符合條件的元素。

此文僅供參考，若要挖掘算法的理論基礎，請點擊A Fast Majority Vote Algorithm

學過hash表的同學看到這個問題通常容易想到使用一個定義一個數組count，其中數組的角標為原來數組的元素值，count數組的元素值代表了這個角標元素出現的次數，由此可以在掃面一遍數組的情況下獲得原數組中各個元素的個數，從而解決此題。也可以利用hash表來替代count數組，這樣做的話算法的魯棒性會更好。