Majority Vote Algorithm

一个学妹问我的问题，让设计时间复杂度为O(nlogn)的算法，找出数组中出现次数超过数组长度一半的值。上网搜了之后发现，其实有更好的解法，Boyer and Moore's Voting Algorithm，降低时间复杂度到O(n)。

1.递归解法(Recursive Method)

function majority ( array A with numer_of_elements N)
{
    if N == 1:
        return A[0]
    let AL, AR be the first halves of A
    let ML = majority(AL)
    let MR = majority(AR)
    if neither half has a majority:
    	return "no majority"
    else:
	check whether either ML or MR is a majority element of A
        if so: return that element
        else: return "no majority"
}

时间复杂度：O(N*logN)

2. Boyer and Moore's Voting Algorithm

#include <stdio.h>
#include <stdlib.h>

int candidate_element(int *array, int n)
{
    int count = 1;
    int curr_candidate = 0;
    int i;
    for(i=0; i<n; i++)
    {
	if(array[i] == array[curr_candidate])
	    ++count;
	else
	    --count;
	if(count == 0)
	{
	    curr_candidate = i;
	    count = 1;
	}
    }
    return array[curr_candidate];
}

int is_majority_element(int *array, int n, int candidate)
{
    int cnt = 0;
    int i;
    for(i=0; i<n; i++)
	if(array[i] == candidate)
	    ++cnt;
    if(cnt > n/2)
	return 1;
    else
	return 0;
}

int main()
{
    int *array;
    int n;
    int i;
    int candidate;
    while(scanf("%d", &n) != EOF)
    {
	array = (int*)malloc(sizeof(int) * n);
        for(i=0; i<n; i++)
	    scanf("%d",array+i);
	
	candidate = candidate_element(array, n);
	if(is_majority_element(array, n, candidate))
	    printf("the majority element is: %d\n", candidate);
	else
	    printf("there is no majority element in the give array\n");
    }
    return 0;
}

时间复杂度：O(N)

形式化证明及分析见此文档: majority vote algorithm.pdf